Longest Substring with K Unique Characters ā Problem Statement & Solution Guide
Problem Description
Given a string s and an integer k, find the length of the longest substring that contains exactly k unique characters.
Examples
Input
abba
Output
2
Explanation: Step-by-step: with input 'abba', we initialize the sliding window [0, 0] with 1 unique character 'a'. We expand the window to [0, 1] with 2 unique characters 'a', 'b'. The longest substring with 2 unique characters is 'ab'. We continue expanding the window to [1, 2] with 2 unique characters 'b', 'a'. The longest substring with 2 unique characters is still 'ab'. We continue expanding the window to [2, 3] with 2 unique characters 'a', 'b'. The longest substring with 2 unique characters is still 'ab'. We continue expanding the window to [3, 4] with 2 unique characters 'b', 'a'. The longest substring with 2 unique characters is still 'ab'. We cannot expand the window further, so the longest substring with 2 unique characters is 'ab' with length 2.
Input
aab
Output
2
Explanation: Step-by-step: with input 'aab', we initialize the sliding window [0, 0] with 1 unique character 'a'. We expand the window to [0, 1] with 2 unique characters 'a', 'b'. The longest substring with 2 unique characters is 'ab'. We continue expanding the window to [1, 2] with 2 unique characters 'b', 'a'. The longest substring with 2 unique characters is still 'ab'. We cannot expand the window further, so the longest substring with 2 unique characters is 'ab' with length 2.
Constraints
- 1 <= k <= 26
- 1 <= s.length <= 10^5
- s consists of only lowercase English letters
Optimal Approach & Strategy
The optimized approach uses a sliding window technique with a frequency map to track the unique characters in the current window, achieving a time complexity of O(n).
Brute Force Approach
The brute-force approach involves checking all possible substrings of the given string and counting the number of unique characters in each substring, resulting in a time complexity of O(nĀ²).
Verified Code Solutions
function longestSubstring(s, k) {
let maxLen = 0, start = 0, charCount = {}, uniqueChars = 0;
for (let end = 0; end < s.length; end++) {
charCount[s[end]] = (charCount[s[end]] || 0) + 1;
if (charCount[s[end]] === 1) uniqueChars++;
while (uniqueChars > k) {
charCount[s[start]]--;
if (charCount[s[start]] === 0) uniqueChars--;
start++;
}
maxLen = Math.max(maxLen, end - start + 1);
}
return maxLen;
}public int longestSubstringWithKUniqueChars(String s, int k) {
int[] charCount = new int[256]; // assuming ASCII characters
int maxLength = 0;
int windowStart = 0;
for (int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
char rightChar = s.charAt(windowEnd);
charCount[rightChar]++;
while (charCount.length > k) {
char leftChar = s.charAt(windowStart);
charCount[leftChar]--;
if (charCount[leftChar] == 0) {
charCount[leftChar] = 0;
}
windowStart++;
}
maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
}
return maxLength;
}def longest_substring_with_k_unique_chars(s: str, k: int) -> int:
char_count = {}
max_length = 0
window_start = 0
for window_end in range(len(s)):
right_char = s[window_end]
if right_char not in char_count:
char_count[right_char] = 0
char_count[right_char] += 1
while len(char_count) > k:
left_char = s[window_start]
char_count[left_char] -= 1
if char_count[left_char] == 0:
del char_count[left_char]
window_start += 1
max_length = max(max_length, window_end - window_start + 1)
return max_lengthfunction longestSubstring(s, k) {
let maxLen = 0, start = 0, charCount = {}, uniqueChars = 0;
for (let end = 0; end < s.length; end++) {
charCount[s[end]] = (charCount[s[end]] || 0) + 1;
if (charCount[s[end]] === 1) uniqueChars++;
while (uniqueChars > k) {
charCount[s[start]]--;
if (charCount[s[start]] === 0) uniqueChars--;
start++;
}
maxLen = Math.max(maxLen, end - start + 1);
}
return maxLen;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.