Longest Substring with At Most Two Distinct Characters

​Given a string s, find the length of the longest substring t that contains at most 2 distinct characters.

Example 1:

Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.

Example 2:

Input: "ddaabbb"
Output: 5
Explanation: t is "aabbb" which its length is 5.

The problem can be solved by the sliding window approach in a single pass. We need to have 2 pointers called left and right as the boundaries of the sliding window. In the beginning both the pointer will point to the 0th position of the String. Then move the right pointer to the right while the window contains not more than two distinct characters. If at some point we’ve got 3 distinct characters, let’s move the left pointer to keep not more than 2 distinct characters in the window. We can use a HashMap containing all characters in the sliding window as keys and their rightmost positions as values. At any moment, this HashMap could contain no more than 3 elements. The following figure is explaining the sliding window concept.

Algorithm

  • Return N if the String length is less than 3.
  • Create two pointers left and right pointing to the 0th position of the String. 
  • Initialize variable max_len = 0. It will keep track of the maximum length Substring.
  • While the right pointer is less than N:
    • If HashMap contains less than 3 distinct characters, add the current character s[right] in the HashMap and move the right pointer to the right.
    • If HashMap contains 3 distinct characters, then remove the leftmost character from the HashMap and move the left pointer so that the sliding window contains not more than 2 distinct characters.
    • Update max_len.
public int lengthOfLongestSubstringTwoDistinct(String s) {
  if (s == null || s.length() == 0)
    return 0;
  if (s.length() < 3) return s.length();
  int l = 0, r = 0, maxLength = 0;
  Map<Character,Integer> dict = new HashMap<>();
  while (r < s.length()) {
    char cur = s.charAt(r);
    dict.put(cur, r);
    r++;
    if (dict.size() == 3) {
      int indexToDelete = Collections.min(dict.values());
      char charToDelete = s.charAt(indexToDelete);
      dict.remove(charToDelete);
      l = (indexToDelete + 1);
    }
    maxLength = Math.max(maxLength, (r - l));
  }
  return maxLength;
}

Complexity Analysis:

  • Time complexity: O(N) where N is the number of characters in the input string.
  • Space complexity: O(1) since additional space is used only for a HashMap with at most 3 elements.

‘ ​

Categories: String

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s