Longest Substring with At Most Two Distinct Characters

Problem

Given a string s, find the length of the longest substring t that contains at most 2 distinct characters.

Examples

Example 1:

1
2
3


Input: "eceba"
Output: 3
Explanation: t is "ece" which its length is 3.

Example 2:

1
2
3


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

Solution

Method 1 – Sliding Window with Hash Map

Intuition

We want the longest substring with at most two distinct characters. As we scan the string, we can use a sliding window to keep track of a valid substring, and a hash map to count the characters in the window. When the window contains more than two distinct characters, we shrink it from the left until it is valid again.

Approach

Use two pointers (left and right) to represent the window.
Expand right to include new characters, updating their count in a hash map.
If the map has more than two keys, move left forward and decrease counts until only two distinct characters remain.
Track the maximum window size throughout.

Code

1
2

##### C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


#include <unordered_map>
#include <string>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstringTwoDistinct(string s) {
        unordered_map<char, int> count;
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.size(); ++right) {
            count[s[right]]++;
            while (count.size() > 2) {
                if (--count[s[left]] == 0) count.erase(s[left]);
                ++left;
            }
            maxLen = max(maxLen, right - left + 1);
        }
        return maxLen;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func lengthOfLongestSubstringTwoDistinct(s string) int {
    count := make(map[byte]int)
    left, maxLen := 0, 0
    for right := 0; right < len(s); right++ {
        count[s[right]]++
        for len(count) > 2 {
            count[s[left]]--
            if count[s[left]] == 0 {
                delete(count, s[left])
            }
            left++
        }
        if right-left+1 > maxLen {
            maxLen = right - left + 1
        }
    }
    return maxLen
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


import java.util.HashMap;

class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        HashMap<Character, Integer> count = new HashMap<>();
        int left = 0, maxLen = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            count.put(c, count.getOrDefault(c, 0) + 1);
            while (count.size() > 2) {
                char leftChar = s.charAt(left);
                count.put(leftChar, count.get(leftChar) - 1);
                if (count.get(leftChar) == 0) count.remove(leftChar);
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    fun lengthOfLongestSubstringTwoDistinct(s: String): Int {
        val count = mutableMapOf<Char, Int>()
        var left = 0
        var maxLen = 0
        for (right in s.indices) {
            count[s[right]] = count.getOrDefault(s[right], 0) + 1
            while (count.size > 2) {
                val leftChar = s[left]
                count[leftChar] = count[leftChar]!! - 1
                if (count[leftChar] == 0) count.remove(leftChar)
                left++
            }
            maxLen = maxOf(maxLen, right - left + 1)
        }
        return maxLen
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class Solution:
    def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
        count = {}
        left = max_len = 0
        for right, c in enumerate(s):
            count[c] = count.get(c, 0) + 1
            while len(count) > 2:
                left_char = s[left]
                count[left_char] -= 1
                if count[left_char] == 0:
                    del count[left_char]
                left += 1
            max_len = max(max_len, right - left + 1)
        return max_len

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


use std::collections::HashMap;

impl Solution {
    pub fn length_of_longest_substring_two_distinct(s: String) -> i32 {
        let s = s.as_bytes();
        let mut count = HashMap::new();
        let (mut left, mut max_len) = (0, 0);
        for right in 0..s.len() {
            *count.entry(s[right]).or_insert(0) += 1;
            while count.len() > 2 {
                let left_char = s[left];
                *count.get_mut(&left_char).unwrap() -= 1;
                if count[&left_char] == 0 {
                    count.remove(&left_char);
                }
                left += 1;
            }
            max_len = max_len.max(right - left + 1);
        }
        max_len as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


function lengthOfLongestSubstringTwoDistinct(s: string): number {
    const count: Record<string, number> = {};
    let left = 0, maxLen = 0;
    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        count[c] = (count[c] || 0) + 1;
        while (Object.keys(count).length > 2) {
            const leftChar = s[left];
            count[leftChar]--;
            if (count[leftChar] === 0) delete count[leftChar];
            left++;
        }
        maxLen = Math.max(maxLen, right - left + 1);
    }
    return maxLen;
}

Complexity

⏰ Time complexity: O(n), where n is the length of s. Each character is visited at most twice (once by right, once by left).
🧺 Space complexity: O(1), since the map holds at most 3 characters (constant size alphabet).

Problem#

Examples#

Solution#

Method 1 – Sliding Window with Hash Map#

Intuition#

Approach#

Code#

Complexity#