Question

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

Given a string s, return the length of the longest substring that contains at most two distinct characters.

Example 1:

Input: s = "eceba"
Output: 3
Explanation: The substring is "ece" which its length is 3.

Example 2:

Input: s = "ccaabbb"
Output: 5
Explanation: The substring is "aabbb" which its length is 5.

Constraints:

1 <= s.length <= 10⁵
s consists of English letters.

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

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); // meaning last iteration is a valid result

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

    }
}

############

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        Map<Character, Integer> cnt = new HashMap<>();
        int n = s.length();
        int ans = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            char c = s.charAt(i);
            cnt.put(c, cnt.getOrDefault(c, 0) + 1);
            while (cnt.size() > 2) {
                char t = s.charAt(j++);
                cnt.put(t, cnt.get(t) - 1);
                if (cnt.get(t) == 0) {
                    cnt.remove(t);
                }
            }
            ans = Math.max(ans, i - j + 1);
        }
        return ans;
    }
}

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

'''
>>> from collections import Counter
>>> c = Counter()
>>> c
Counter()
>>> c['a'] += 1
>>> c
Counter({'a': 1})


>>> c
Counter({'a': 1, 'c': 1, 'b': 1})
>>> c.pop(2)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: 2
>>>
>>> c.pop('c')
1
>>> c
Counter({'a': 1, 'b': 1})
'''
class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        cnt = Counter() # or, cnt = defaultdict(int)
        ans = i = 0
        for j, c in enumerate(s):
            cnt[c] += 1
            while len(cnt) > 2:
                cnt[s[i]] -= 1
                if cnt[s[i]] == 0:
                    cnt.pop(s[i])
                i += 1
            ans = max(ans, j - i + 1)
        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

func lengthOfLongestSubstringTwoDistinct(s string) (ans int) {
	cnt := map[byte]int{}
	j := 0
	for i := range s {
		cnt[s[i]]++
		for len(cnt) > 2 {
			cnt[s[j]]--
			if cnt[s[j]] == 0 {
				delete(cnt, s[j])
			}
			j++
		}
		ans = max(ans, i-j+1)
	}
	return
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

159 - Longest Substring with At Most Two Distinct Characters

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions