Facebook Pixel

Longest Substring with At Most Two Distinct Characters

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.

Solution

Since we don't know the size of the window, we will apply the flexible sliding window template. We will keep a last_occurrence hashmap that stores the last occurence of a character in the current window. Every time the right pointer reaches a new character, we update that character's last occurrence to r. In every iteration, we will check whether the current window is longer than max_len. This means that whenever the window becomes invalid, we must update the window first before the check. We will update l when condition(window) evaluates to true. Here, condition(window) is when the hashmap contains three characters. We must discard the entirety of one character c, which means we will choose the smaller last_occurrence[c] to maintain a longers substring. So the new left pointer is updated to min(last_occurrence.values())+1 and we will delete this character from the last_occurrence hashmap.

Implementation

def lengthOfLongestSubstringTwoDistinct(self, s):
    last_occurrence = dict()
    max_len, l = 0, 0
    for r in range(len(s)):
        last_occurrence[s[r]] = r
        r += 1
        if len(last_occurrence) == 3:
            l = min(last_occurrence.values())+1
            del last_occurrence[s[l-1]]
        max_len = max(max_len, r - l)
    return max_len
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

We want to use a sliding window to find the substrings with two distint characters.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More