Description

Given a string s, return the length of the longest substring that contains at most two distinct characters.

Example 1:

1Input: s = "eceba"
2Output: 3
3Explanation: The substring is "ece" which its length is 3.

Example 2:

1Input: s = "ccaabbb"
2Output: 5
3Explanation: The substring is "aabbb" which its length is 5.

Constraints:

  • 1 <= s.length <= 10^5
  • s consists of English letters.

Solution

This also looks like sliding window problem. In order to track 2 distinct characters, we can use HashMap to store those characters as keys. As long as keys count is less or equal to 2, we can continue counting the longest substring. When it becomes more than 2, our window becomes invalid, at this point, we have to remove the characters located at left pointer.

 1class Solution {
 2    public int lengthOfLongestSubstringTwoDistinct(String s) {
 3        if (s.length() < 3)
 4            return s.length();
 5        int left = 0, right = 0, maxLength = 0;
 6        Map<Character, Integer> map = new HashMap<>();
 7        while (right < s.length()) {
 8            char c = s.charAt(right);
 9            map.put(c, map.getOrDefault(c, 0) + 1);
10            while (map.size() > 2) {
11                char leftChar = s.charAt(left);
12                map.put(leftChar, map.get(leftChar) - 1);
13                if (map.get(leftChar) == 0) {
14                    map.remove(leftChar);
15                }
16                left++;
17            }
18            maxLength = Math.max(maxLength, right - left + 1);
19            right++;
20        }
21        return maxLength;
22    }
23}
  • Time Complexity: O(n)
  • Space Complexity: O(1) since we can have at most 3 keys in HashMap before we start reducing its size.