Longest Substring with At Most Two Unique Characters

1

given a string ,return the longest substring that contains at most two unique
characters.

public int maxLength(String s){
        if (s.isEmpty()) return 0;
      //diffCharIndex 是从右往左起第一个不同字符的位置。
      //currentLength是以当前扫描位置字符为最后一个字符的符合条件的字符长度
        int diffCharIndex = -1, currentLength = 1, maxLength = 1;
        for (int i = 1; i < s.length(); i++)
        {
            if (s.charAt(i) != s.charAt(i-1))
            {
                 if (diffCharIndex == -1 || s.charAt(i) == s.charAt(diffCharIndex)) {
                    currentLength++;  }
                else { currentLength = i - diffCharIndex; }
                diffCharIndex = i-1;
            }
            else currentLength++;
            if (currentLength > maxLength) maxLength = currentLength;
        }
        return maxLength;
    }

下面的修改为返回字符串

  string maxLength(string s){
      if (s.empty()) return 0;
      int diffCharIndex = -1, currentLength = 1, maxLength = 1;
      int maxStart=0;
      for (int i = 1; i < s.length(); i++)
      {
          if (s[i] != s[i-1])
          {
              if (diffCharIndex == -1 || s[i] == s[diffCharIndex]) {
                  currentLength++;  }
              else { currentLength = i - diffCharIndex;  }
              diffCharIndex = i-1;
          }
          else currentLength++;
          if (currentLength > maxLength) {maxLength = currentLength; maxStart=i-currentLength+1;}
      }
      return s.substr(maxStart,maxLength);
  }

2
Longest Substring Of Two Unique Characters
Find the longest run of consecutive characters in a string that contains only two unique characters; if there is a tie, return the rightmost. For instance, given input string abcabcabcbcbc, the longest run of two characters is the 6-character run of bcbcbc that ends the string.


Here is a O(N) solution written in C#:
public static string GetLongestSubset(string str) {
            if (str == null)
                throw new ArgumentNullException ("str");

            if (str.Length == 0)
                return String.Empty;
        
            int s1 = 0, s2 = 0;

            // Get next unique char
            for(int i = 1; i < str.Length; i++) {
                if (str [i] != str[s1]) {
                    s2 = i;
                    break;
                }
            }

            if (s2 == 0)
                return str; // all chars are the same

            int sequenceStart = 0;
            int maxStart = 0, maxEnd = 0;
            int maxDiff = 0;

            // Scan for longest sequences
            for (int i = s2 + 1; i < str.Length; i++) {
                // Can this new char belong to the current substring we are building up?
                if (str [i] != str [s1] && str [i] != str [s2]) {
                    int diff = i - sequenceStart;
                    if (diff >= maxDiff) {
                        maxDiff = diff;
                        maxStart = sequenceStart;
                        maxEnd = i - 1;
                    }
                    if (s1 > s2) {
                        sequenceStart = s1;
                        s2 = i;
                    } else {
                        sequenceStart = s2;
                        s1 = i;
                    }
                } else if (str [i] != str [i - 1]) {
                    // Track start of each char sequence containing the same char
                    if (str [i] == str [s1]) {
                        s1 = i;
                    } else {
                        s2 = i;
                    }
                }
            }

            int lastDiff = str.Length - sequenceStart;
            if (lastDiff >= maxDiff) {
                maxDiff = lastDiff;
                maxStart = sequenceStart;
                maxEnd = str.Length - 1;
            }

            return str.Substring (maxStart, (maxEnd - maxStart) + 1);
        }