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

For example, Given s =

`“eceba”`

,
T is "ece" which its length is 3.

**Understand the problem:**

The problem looks quite similar to a previous problem:

The idea is still to use two pointers, i and j. We move the pointer i forward and put the visited character as well as its times into a map. We also need to increase the counter if the character is not in the map.

When the counter is greater than 2, we need to move the second pointer j and try to decrease the counter. However, we cannot just decrease the counter by 1 once we move the j pointer a step forward. e.g. b e c e a. When the i pointer is at a, and j pointer is at e, move the j pointer from e to c does not decrease the counter (still 3). Therefore, the condition to decrease the counter is when the character is not in the map again.

**Code (Java):**

public class Solution { public int lengthOfLongestSubstringTwoDistinct(String s) { if (s == null || s.length() < 3) { return s.length(); } Map<Character, Integer> map = new HashMap<Character, Integer>(); int maxLen = 0; int j = 0; int counter = 0; for (int i = 0; i < s.length(); i++) { char element = s.charAt(i); if (!map.containsKey(element)) { counter++; map.put(element, 1); while (j < i && counter > 2) { if (map.get(s.charAt(j)) == 1) { map.remove(s.charAt(j)); } else { int tmp = map.get(s.charAt(j)) - 1; map.put(s.charAt(j), tmp); } if (!map.containsKey(s.charAt(j))) { counter--; } j++; } } else { int tmp = map.get(s.charAt(i)); map.put(s.charAt(i), tmp + 1); } maxLen = Math.max(maxLen, i - j + 1); } return maxLen; } }

**Analysis:**

Time complexity is O(n) since we only move the pointers forward. The space complexity is at O(k) where k the number of distinct numbers in the substring. In this case, k is 2.

**Update on 10/13/15:**

public class Solution { public int lengthOfLongestSubstringTwoDistinct(String s) { if (s == null || s.length() == 0) { return 0; } Map<Character, Integer> map = new HashMap<>(); int j = 0; int i = 0; int len = 0; for (i = 0; i < s.length(); i++) { char c = s.charAt(i); if (!map.containsKey(c)) { map.put(c, i); } else { int pos = map.get(c); map.put(c, i); } if (map.size() > 2) { len = Math.max(len, i - j); // Then shrink the window size while (map.size() > 2) { if (map.containsKey(s.charAt(j)) && map.get(s.charAt(j)) == j) { map.remove(s.charAt(j)); } j++; } } } if (j < s.length()) { len = Math.max(len, i - j); } return len; } }

## No comments:

## Post a Comment