Longest Substring with At Most Two Distinct Characters solution and explanation
Google
9 more videos on this problem
[Java] Leetcode 159. Longest Substring with At Most Two Distinct Characters [Sliding Windows #2]Eric Programming · 10:45 · 10K views
Longest Substring with At Most Two Distinct Characters - LeetCode 159 - PythonDeepti Talesra · 11:35 · 9K views
LeetCode in Python 159. Longest Substring with At Most Two Distinct Characters - Michelle小梦想家Michelle小梦想家 · 17:41 · 582 views
159. Longest Substring with At Most Two Distinct Characters - Week 4/5 Leetcode December ChallengeProgramming Live with Larry · 4:37 · 455 views
159. Longest Substring with At Most Two Distinct Characters - Week 1/5 Leetcode April ChallengeProgramming Live with Larry · 8:27 · 384 views
[Leetcode] 159. Longest Substring with At Most Two Distinct CharactersSimple Code · 6:42 · 275 views
LeetCode 159/340: Longest Substring with At Most Two/K Distinct CharactersKevin Dai · 6:30 · 194 views
LeetCode 159 | Longest Substring with At Most Two Distinct Characters | 2 Pointers | HashMap | JavaSleepy Cracker · 7:03 · 151 views
Leetcode 159. Longest Substring with At Most Two Distinct Characters (sliding window 340)LetsCode · 7:20 · 101 views
LINKEDIN Coding Interview Question - Longest Substring with Most Two Distinct Characters | LeetCodeJeanTheCoder · 13:26 · 201 views
The problem
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 <= 105sconsists of English letters.
Approach overview
Problem Overview: Given a string s, return the length of the longest substring that contains at most two distinct characters. The substring must be contiguous, so the goal is to scan the string while keeping track of how many unique characters appear in the current window.
Approach 1: Brute Force Enumeration (O(n^2) time, O(1) space)
Start every substring at index i and extend it character by character while tracking distinct characters with a small frequency map. As soon as the substring contains more than two unique characters, stop extending that window and move to the next starting index. During each expansion, update the maximum substring length that satisfies the constraint. This approach is straightforward and helps verify the constraint logic, but it repeatedly reprocesses overlapping substrings, making it inefficient for large inputs.
Approach 2: Sliding Window with Hash Map (O(n) time, O(1) space)
The optimal strategy uses the sliding window technique combined with a hash table. Maintain two pointers left and right that represent the current window. As you move right across the string, update a frequency map that counts how many times each character appears in the window.
If the map contains more than two distinct characters, the window becomes invalid. Shrink the window from the left by incrementing left and decrementing counts in the map until only two unique characters remain. At each step where the constraint is satisfied, update the maximum window length using right - left + 1.
The key insight: every character enters the window once and leaves once, so the two pointers each move at most n times. This guarantees linear time complexity. The frequency map stores at most three characters at any moment, so the space usage stays constant.
This pattern appears frequently in string and substring problems where the goal is to maintain a window that satisfies a constraint on distinct elements. Once you recognize the pattern, the implementation becomes a standard template.
Recommended for interviews: The sliding window solution is the expected answer. Interviewers want to see that you recognize the “at most K distinct characters” pattern and immediately move to a two-pointer window with a frequency map. Mentioning the brute force approach briefly shows that you understand the problem space, but implementing the O(n) sliding window demonstrates strong algorithmic intuition and familiarity with common substring optimization techniques.
Solution
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
cnt = Counter()
ans = j = 0
for i, c in enumerate(s):
cnt[c] += 1
while len(cnt) > 2:
cnt[s[j]] -= 1
if cnt[s[j]] == 0:
cnt.pop(s[j])
j += 1
ans = max(ans, i - j + 1)
return ansclass 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;
}
};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
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^2) | O(1) | Useful for understanding the constraint logic or when input size is very small |
| Sliding Window + Hash Map | O(n) | O(1) | Best general solution for substring problems with at most K distinct characters |
| Sliding Window with Last Seen Index | O(n) | O(1) | When you want to track the most recent index of characters instead of frequencies |
Frequently asked questions
Is Longest Substring with At Most Two Distinct Characters easy or hard?
The problem is rated Medium because it requires recognizing the sliding window pattern and maintaining a dynamic constraint on distinct characters. Once you know the 'at most K distinct characters' template, the implementation becomes straightforward.
Longest Substring with At Most Two Distinct Characters Python/Java solution
Implement a sliding window with a dictionary in Python or a HashMap in Java. Expand the right pointer to include characters and update counts, then shrink the left pointer when more than two distinct characters appear. Track the maximum window length during the traversal.
How to solve Longest Substring with At Most Two Distinct Characters in O(n)?
Use a sliding window with two pointers. Move the right pointer across the string while updating a frequency map of characters in the window. When the number of distinct characters exceeds two, move the left pointer forward and decrease counts until the window becomes valid again.
What is the best approach for Longest Substring with At Most Two Distinct Characters?
The best approach uses a sliding window with a hash table to track character frequencies. Two pointers expand and shrink the window while maintaining at most two distinct characters. Each character is processed once, giving O(n) time complexity and O(1) space.
Is Longest Substring with At Most Two Distinct Characters asked at Google/Amazon/Meta?
Substring problems using sliding window patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variations include 'at most K distinct characters' or 'longest substring without repeating characters'. Recognizing the sliding window template is key for these interviews.
What data structure is used in Longest Substring with At Most Two Distinct Characters?
A hash table (or dictionary/map) stores the frequency of characters inside the current sliding window. Combined with two pointers, this structure allows constant‑time updates and quick checks on how many distinct characters exist in the window.
What is the time complexity of Longest Substring with At Most Two Distinct Characters?
The optimal sliding window solution runs in O(n) time because each character enters and leaves the window at most once. Space complexity is O(1) since the hash map stores at most three characters while enforcing the two‑distinct constraint.