Given a string `s`

, find the length of the longest substring `t`

that contains at most 2 distinct characters.

**Example 1:**

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

**Example 2:**

Input:"ddaabbb"Output:5Explanation: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 `0`

position of the String. Then move the ^{th}`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`0`

position of the String.^{th} - 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`

.

- If

```
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