Welcome to Subscribe On Youtube

159. Longest Substring with At Most Two Distinct Characters

Description

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 <= 105
  • s consists of English letters.

Solutions

This problem is solved using the sliding window technique alongside a counter (from collections module) to keep track of the frequency of each character within the current window. Here’s a breakdown of how the code works:

Code Breakdown:

  1. Initialization:
    • cnt: A Counter object (which could also be a defaultdict(int) from the collections module) used to track the number of occurrences of each character within the current window of the string.
    • ans: An integer variable used to store the length of the longest valid substring found so far.
    • i: An integer variable used as the start index of the current window. Initially set to 0.
  2. Main Loop:
    • The code iterates over the string s with enumerate, which provides both the index j and the character c at that index.
    • For each character c, its count is incremented in cnt.
    • If the window (from i to j) contains more than two distinct characters (len(cnt) > 2), the code enters a while loop to shrink the window from the left until it contains at most two distinct characters. This is done by:
      • Decreasing the count of the character at the start of the window (s[i]).
      • If the count of s[i] becomes 0, it means this character is no longer in the current window, so it is removed from cnt.
      • Incrementing i to shrink the window from the left.
  3. Update Answer:
    • After possibly shrinking the window to ensure it contains at most two distinct characters, ans is updated to be the maximum of its current value and the length of the current window (j - i + 1).
  4. Return:
    • After iterating through the entire string, the function returns ans, which holds the length of the longest substring containing at most two distinct characters.

Example:

Consider s = "eceba":

  • When j = 2 (s[0:3] = "ece"), the window contains two distinct characters, so ans is updated to 3.
  • When j = 3 (s[0:4] = "eceb"), the window now has three distinct characters. The inner while loop shrinks the window to "ceb", and ans remains 3.
  • The process continues until the end of the string, with the window being adjusted as necessary to ensure it never contains more than two distinct characters.
  • 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;
    }
}

  • class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char, int> cnt;
        int n = s.size();
        int ans = 0;
        for (int i = 0, j = 0; i < n; ++i) {
            cnt[s[i]]++;
            while (cnt.size() > 2) {
                cnt[s[j]]--;
                if (cnt[s[j]] == 0) {
                    cnt.erase(s[j]);
                }
                ++j;
            }
            ans = max(ans, i - j + 1);
        }
        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})
'''

from collections import Counter

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: # shrink
                cnt[s[i]] -= 1
                if cnt[s[i]] == 0:
                    cnt.pop(s[i])
                i += 1
            ans = max(ans, j - i + 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
}

All Problems

All Solutions