Question

Formatted question description: https://leetcode.ca/all/159.html

 159	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: tis "ece" which its length is 3.

 Example 2:

 Input: "ccaabbb"
 Output: 5
 Explanation: tis "aabbb" which its length is 5.

 @tag-string
 @tag-2pointers

Algorithm

Use HashMap to do it, HashMap records the number of occurrences of each character,

Then if the number of mappings in HashMap exceeds two, one mapping needs to be deleted here.

For example "eceba", there are 2 e in the HashMap and 1 c in the HashMap. At this time, b is also stored in the HashMap, then there are three pairs of mappings. At this time, left is 0, and the mapping value is reduced by 1. There is one more e, do not delete it, and left is incremented by 1. At this time, there are three pairs of mappings in the HashMap. At this time, left is 1, then c is reached, and the mapping value is reduced by 1. At this time, e is mapped to 0, e is deleted from the HashMap, left is incremented by 1, and the result is updated to i - left + 1.

And so on until the entire string is traversed.

Code

Java

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Longest_Substring_with_At_Most_Two_Distinct_Characters {

    public static void main(String[] args) {
        Longest_Substring_with_At_Most_Two_Distinct_Characters out = new Longest_Substring_with_At_Most_Two_Distinct_Characters();
        Solution s = out.new Solution();

        System.out.println(s.lengthOfLongestSubstringTwoDistinct("eceba"));
        System.out.println(s.lengthOfLongestSubstringTwoDistinct("ccaabbb"));
    }

    // refer to:
    //       Longest_Substring_with_At_Most_K_Distinct_Characters

    public class Solution {
        /**
         * @param s: a string
         * @return: the length of the longest substring T that contains at most 2 distinct characters
         */
        public int lengthOfLongestSubstringTwoDistinct(String s) {
            if (s == null || s.length() == 0) {
                return 0;
            }

            // char => its count in window
            Map<Character, Integer> map = new HashMap<>();
            int maxLen = 0;
            int left = 0;
            int right = 0;

            while (right < s.length()) {
                char c = s.charAt(right);
                if (map.containsKey(c)) {
                    map.put(c, map.get(c) + 1);
                } else {
                    map.put(c, 1);
                }

                // if distinct chars more than k
                if (map.size() > 2) {
                    maxLen = Math.max(maxLen, right - left);

                    // shrink the window size
                    while (map.size() > 2) { // can be done by another counter variable
                        char leftChar = s.charAt(left);
                        int freq = map.get(leftChar);
                        if (freq == 1) {
                            map.remove(leftChar); // @note: remove by key
                        } else {
                            map.put(leftChar, freq - 1);
                        }
                        left++;
                    }
                }

                right++;
            }

            // @note: final check
            if (left < s.length()) {
                maxLen = Math.max(maxLen, right - left);
            }

            return maxLen;
        }
    }

    public class Solution_arrayAsMap {

        public int lengthOfLongestSubstringTwoDistinct(String s) {

            int[] countMap = new int[256];
            Set<Character> hs = new HashSet<>();

            int result = 0;
            int left = 0;
            int right = 0;

            while (right < s.length()) {

                char c = s.charAt(right);
                countMap[c]++;
                hs.add(c);

                if (hs.size() > 2) {

                    result = Math.max(result, right - left);

                    while (hs.size() > 2) {
                        if (--countMap[s.charAt(left)] == 0) {
                            hs.remove(s.charAt(left));
                        }
                        left++;
                    }
                }

                right++;
            }

            // @note: final check
            if (left < s.length()) {
                result = Math.max(result, right - left);
            }

            return result;
        }

    }
}

// OJ: https://leetcode.com/problems/longest-substring-with-at-most-two-distinct-characters/
// Time: O(N)
// Space: O(C) 
class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        vector<int> m(128, 0);
        int i = 0, j = 0, ans = 0, cnt = 0;
        while (j < s.size()) {
            if (m[s[j++]]++ == 0) ++cnt;
            while (cnt > 2) {
                if (m[s[i++]]-- == 1) --cnt;
            }
            ans = max(ans, j - i);
        }
        return ans;
    }
};

class Solution(object):
  def lengthOfLongestSubstringTwoDistinct(self, s):
    """
    :type s: str
    :rtype: int
    """
    return self.lengthOfLongestSubstringKDistinct(s, 2)

  def lengthOfLongestSubstringKDistinct(self, s, k):
    """
    :type s: str
    :type k: int
    :rtype: int
    """
    if k == 0:
      return 0
    ans = 0
    j = 0
    score = 0
    chashmap = {}
    for i in range(0, len(s)):
      while j < len(s) and (score < k or chashmap.get(s[j], 0) != 0):
        if chashmap.get(s[j], 0) == 0:
          score += 1
        chashmap[s[j]] = chashmap.get(s[j], 0) + 1
        j += 1

      ans = max(ans, j - i)
      chashmap[s[i]] -= 1
      if chashmap[s[i]] == 0:
        score -= 1
    return ans

159 - Longest Substring with At Most Two Distinct Characters

Question

Algorithm

Code

All Problems

All Solutions