Leetcode: Longest Substring with At Most Two Distinct Characters

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:

http://buttercola.blogspot.com/2014/08/leetcode-longest-substring-without.html

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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

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:

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

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;      } }