Longest Substring with At Most K Distinct Characters Solution
Longest Substring with At Most K Distinct Characters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Longest Substring with At Most K Distinct Characters is a medium coding problem on strings, hash table and sliding window, asked in Amazon, Google and Paytm interviews.
- Difficulty: Medium
- Topics: Strings, Hash Table, Sliding Window
- Asked at: Amazon, Google, Paytm
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Return the length of the longest substring of s that contains at most k distinct characters.
Example 1
Input: s = "codekairo", k = 3
Output: 3
Explanation: No window of four keeps the alphabet down to three here.
Example 2
Input: s = "eceba", k = 2
Output: 3
Explanation: "ece".
Example 3
Input: s = "aa", k = 1
Output: 2
Constraints
1 <= s.length <= 1000000 <= k <= 50s consists of English letters.
Hints for Longest Substring with At Most K Distinct Characters
Hint 1
Same window as the two-distinct version, with the bound taken as a parameter.
Hint 2
k = 0admits only the empty substring — answer 0.Hint 3
Keep a tally and a distinct counter so each step is constant time.
How to solve Longest Substring with At Most K Distinct Characters
Generalise the two-distinct window: grow on the right, and while the distinct count exceeds k, shrink from the left. The tally makes each update constant time.
Approach
- Handle
k = 0up front by returning 0. - Add
s[r]to the tally, raising the distinct count when it enters. - While the distinct count exceeds
k, removes[l]and advancel. - Track the longest valid window.
Why it works
Shrinking a window can only lower its distinct count, so for a fixed right edge the valid left edges are a suffix — the hallmark of a two-pointer window. Every index is added and removed once, so the scan is linear regardless of k.
Complexity
- Time —
O(n) - Space —
O(min(n, alphabet))
Pitfalls
k = 0must not fall through into the loop, where the shrink would run past the right edge.- Forgetting to decrement the distinct count on a zero tally silently caps the window.
- The answer is a length, not a count of substrings.
Reference solution
Python
def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
if k == 0:
return 0
cnt = {}
distinct = 0
l = 0
best = 0
for r, c in enumerate(s):
cnt[c] = cnt.get(c, 0) + 1
if cnt[c] == 1:
distinct += 1
while distinct > k:
u = s[l]
cnt[u] -= 1
if cnt[u] == 0:
distinct -= 1
l += 1
best = max(best, r - l + 1)
return bestJava
public static int lengthOfLongestSubstringKDistinct(String s, int k) {
if (k == 0) return 0;
int[] cnt = new int[128];
int distinct = 0, l = 0, best = 0;
for (int r = 0; r < s.length(); r++) {
if (cnt[s.charAt(r)]++ == 0) distinct++;
while (distinct > k) {
if (--cnt[s.charAt(l)] == 0) distinct--;
l++;
}
best = Math.max(best, r - l + 1);
}
return best;
}C++
int lengthOfLongestSubstringKDistinct(string s, int k) {
if (k == 0) return 0;
vector<int> cnt(128, 0);
int distinct = 0, l = 0, best = 0;
for (int r = 0; r < (int) s.size(); r++) {
if (cnt[(int) s[r]]++ == 0) distinct++;
while (distinct > k) {
if (--cnt[(int) s[l]] == 0) distinct--;
l++;
}
best = max(best, r - l + 1);
}
return best;
}JavaScript
var lengthOfLongestSubstringKDistinct = function(s, k) {
if (k === 0) return 0;
var cnt = {};
var distinct = 0, l = 0, best = 0;
for (var r = 0; r < s.length; r++) {
var c = s.charAt(r);
cnt[c] = (cnt[c] || 0) + 1;
if (cnt[c] === 1) distinct++;
while (distinct > k) {
var u = s.charAt(l);
cnt[u]--;
if (cnt[u] === 0) distinct--;
l++;
}
if (r - l + 1 > best) best = r - l + 1;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Hashing: Hash Maps and Hash Sets