Online Judge Solutions

Wednesday, May 29, 2013

Longest substring which begins and ends with two unique characters

This is follow up my last post at Longest substring which contains just two unique characters

What if you are asked to find the longest substring which begins and ends with unique characters. For example, the following strings begin and end with unique characters:
  "abc" where 'a' and 'c' are unique
  "ebbcf" where 'e' and 'f' are unique

Here is my solution in (C#):
 

// ----------------------------------------------------------------------------
// Copyright (c) SimpleCoder 2013
// ----------------------------------------------------------------------------
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace LongestSubstring
{
 static class Program
 {
    // Find longest substring which begins and ends with unique characters. 
    // i.e. "abc" where 'a' and 'c' are unique
    // "ebbcf" where 'e' and 'f' are unique
    static string LongestSubstring(string str)
    {
        int Len = str.Length;
        // start index of current substring
        int i = 0;
        // end index of current substring
        int j = 0;
        // start index of the longest substring 
        int maxStart = 0;
        // length of the longest substring 
        int maxLen = 0;
        // Occurrence of each char in current substring
        Dictionary<char, int> CountMap = new Dictionary<char, int>();

        while (j < Len)
        {
            char ch = str[j];            
            // add current char into CountMap
            if (!CountMap.ContainsKey(ch))
                CountMap.Add(ch, 1);            else
                ++CountMap[ch];
            // Increment i until the occurrence of str[i] is 1 or i reaches j
            char ch2 = str[i];
            while (i < j && CountMap[ch2] > 1)
            {
                --CountMap[ch2];
                ch2 = str[++i];
            }
            // Update maxStart and maxLen if current substring is the longest one
            // which starts and ends with unique characters.
            if (i < j && CountMap[ch] == 1 && CountMap[str[i]] == 1 &&
                j - i >= maxLen)
            {
                maxStart = i;
                maxLen = j - i + 1;
            }
            ++j;
         }
          return str.Substring(maxStart, maxLen);
     }
     static void Main()
     {          Assert.AreEqual("", LongestSubstring(""));
          Assert.AreEqual("", LongestSubstring("a"));
          Assert.AreEqual("ab", LongestSubstring("ab"));
          Assert.AreEqual("abc", LongestSubstring("abc"));
          Assert.AreEqual("abbc", LongestSubstring("abbc"));
          Assert.AreEqual("bac", LongestSubstring("abac"));
          Assert.AreEqual("bcccccaaaccccd", LongestSubstring("abaaabcccccaaaccccdd"));
     }
   }
} 

No comments:

Post a Comment