# 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