Longest Substring with K Unique Characters — Problem Statement & Solution Guide

StringsMediumSliding Window

TimeO(n)

SpaceO(1) or O(σ) where σ is alphabet size

Quick Answer & Algorithm Key Takeaway

Master coding challenges related to Strings and solve the Longest Substring with K Unique Characters problem optimally.

TopicStrings

PatternSliding Window

TimeO(n)

SpaceO(1) or O(σ) where σ is alphabet size

Problem Description

You are provided with a string s consisting of lowercase English letters and an integer k. Your task is to determine the length of the longest contiguous substring within s that contains exactly k distinct characters. If no such substring exists, return 0.

A substring is defined as a contiguous sequence of characters within the string. The uniqueness of characters is determined by their identity; for example, the substring "aab" contains exactly two unique characters: 'a' and 'b'.

The solution should efficiently process the string to identify the maximum length satisfying the uniqueness constraint without resorting to brute-force enumeration of all possible substrings.

DSA Pattern Breakdown

"Longest Substring with K Unique Characters"

medium

WHY DOES IT MATTER?

The sliding‑window pattern is essential for any problem that asks for an optimal subarray or substring under a constraint that can be updated incrementally. It transforms exponential or quadratic brute‑force scans into linear passes, which is critical for real‑time systems and large‑scale data processing.

OPTIMIZATION CHALLENGE

The key insight is recognizing that the number of distinct characters in a window is a monotonic function of the window size; therefore, we can safely move the left pointer only when the distinct count exceeds k, ensuring each character is visited at most twice.

REAL-WORLD CONNECTION

Think of a network router buffering packets: it continuously adds incoming packets (right pointer) and drops the oldest ones (left pointer) to keep the buffer within a bandwidth or protocol constraint. The router must do this in O(1) per packet to avoid latency spikes, mirroring the sliding‑window's constant‑time adjustments.

During an interview, first write the frequency map update logic clearly, then handle the three cases—<k, =k, >k—separately. This keeps the code readable and avoids off‑by‑one bugs when shrinking the window.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1) or O(σ) where σ is alphabet size

Core Theory — Why This Approach?

The problem asks for the longest contiguous substring that contains exactly k distinct characters. A naive solution would enumerate all O(n^2) substrings and count distinct characters for each, leading to O(n^3) time in the worst case, which is infeasible for large strings. The optimal paradigm leverages the sliding‑window (two‑pointer) technique combined with a hash map (or fixed‑size array for lowercase letters) to maintain the frequency of characters inside the current window. By expanding the right pointer and shrinking the left pointer only when the distinct‑character count exceeds k, we can guarantee that each character is processed a constant number of times, yielding linear time. This approach exploits the monotonic property that expanding a window never reduces the number of distinct characters, allowing us to adjust the window efficiently while preserving the exact‑k constraint.

Interview Questions on This Problem

Q1How would you modify the sliding‑window solution to return the actual substring(s) of maximum length instead of just the length?

Maintain variables for the best length and a list of start indices. Whenever the current window size equals the best length, append the start index; if it exceeds, clear the list and store the new start. After the scan, slice the original string using the stored indices to produce all maximal substrings.

Q2What changes are needed if the input string can contain Unicode characters beyond lowercase English letters?

Replace the fixed‑size 26‑element array with a hash map (e.g., unordered_map<char,int> in C++ or dict in Python) to track frequencies, because the character set size is no longer bounded. The rest of the sliding‑window logic remains identical.

Q3Can you solve the problem in O(n) time and O(1) extra space when the alphabet size is constant? Explain.

Yes. Since the alphabet is limited (e.g., 26 lowercase letters), we can use a static integer array of size 26 for frequencies, which counts as O(1) space. The sliding‑window still runs in O(n) because each pointer moves at most n steps.

Examples

Example 1

Input

s = "eceba", k = 2

Output

Explanation: The substrings with exactly 2 unique characters are "ece" (unique: e, c), "ceb" (unique: c, e, b - wait, 3 unique), "eba" (unique: e, b, a - 3 unique). Let's re-evaluate. "ece" has {e, c} -> 2 unique. Length 3. "ceb" has {c, e, b} -> 3 unique. "eba" has {e, b, a} -> 3 unique. "ce" has {c, e} -> 2 unique. Length 2. "eb" has {e, b} -> 2 unique. Length 2. "ba" has {b, a} -> 2 unique. Length 2. The longest is "ece" with length 3.

Example 2

Input

s = "aaabbb", k = 1

Output

Explanation: We need substrings with exactly 1 unique character. The string consists of three 'a's followed by three 'b's. The longest substring with only 'a' is "aaa" (length 3). The longest substring with only 'b' is "bbb" (length 3). Any substring crossing the boundary, like "aab", has 2 unique characters. Thus, the maximum length is 3.

Example 3

Input

s = "abcabc", k = 3

Output

Explanation: The entire string "abcabc" contains the unique characters {a, b, c}, which is exactly 3. Since the whole string satisfies the condition, the length is 6. No longer substring exists.

Example 4

Input

s = "aabbcc", k = 2

Output

Explanation: We look for substrings with exactly 2 unique characters. "aabb" has {a, b} -> 2 unique, length 4. "bbcc" has {b, c} -> 2 unique, length 4. "aabbcc" has {a, b, c} -> 3 unique. "abbc" has {a, b, c} -> 3 unique. The maximum length found is 4.

Constraints

1 <= s.length <= 10^5
s consists of lowercase English letters only
1 <= k <= 26

Optimal Approach & Strategy

Use a sliding window with a frequency map, expanding the right edge and shrinking the left edge only when the distinct count exceeds k, updating the answer when the count equals k.

Brute Force Approach

Generate every possible substring, count its distinct characters, and keep the longest that has exactly k distinct letters.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestSubstringWithKUnique = function(s, k) {
    if (k === 0) return 0;
    
    let maxLen = 0;
    let left = 0;
    const charCount = new Map();
    
    for (let right = 0; right < s.length; right++) {
        const char = s[right];
        charCount.set(char, (charCount.get(char) || 0) + 1);
        
        while (charCount.size > k) {
            const leftChar = s[left];
            charCount.set(leftChar, charCount.get(leftChar) - 1);
            if (charCount.get(leftChar) === 0) {
                charCount.delete(leftChar);
            }
            left++;
        }
        
        if (charCount.size === k) {
            maxLen = Math.max(maxLen, right - left + 1);
        }
    }
    
    return maxLen;
};

class Solution {
public:
    int longestSubstringWithKUnique(const std::string& s, int k) {
        if (k == 0) return 0;
        
        int n = s.size();
        int maxLen = 0;
        int left = 0;
        std::unordered_map<char, int> charCount;
        
        for (int right = 0; right < n; ++right) {
            charCount[s[right]]++;
            
            while (charCount.size() > k) {
                charCount[s[left]]--;
                if (charCount[s[left]] == 0) {
                    charCount.erase(s[left]);
                }
                left++;
            }
            
            if (charCount.size() == k) {
                maxLen = std::max(maxLen, right - left + 1);
            }
        }
        
        return maxLen;
    }
};

class Solution {
    public int longestSubstringWithKUnique(String s, int k) {
        if (k == 0) return 0;
        
        int maxLen = 0;
        int left = 0;
        int[] charCount = new int[26];
        int uniqueCount = 0;
        
        for (int right = 0; right < s.length(); right++) {
            int charIndex = s.charAt(right) - 'a';
            if (charCount[charIndex] == 0) {
                uniqueCount++;
            }
            charCount[charIndex]++;
            
            while (uniqueCount > k) {
                int leftCharIndex = s.charAt(left) - 'a';
                charCount[leftCharIndex]--;
                if (charCount[leftCharIndex] == 0) {
                    uniqueCount--;
                }
                left++;
            }
            
            if (uniqueCount == k) {
                maxLen = Math.max(maxLen, right - left + 1);
            }
        }
        
        return maxLen;
    }
}

class Solution:
    def longestSubstringWithKUnique(self, s: str, k: int) -> int:
        if k == 0:
            return 0
        
        max_len = 0
        left = 0
        char_count = {}
        
        for right in range(len(s)):
            char = s[right]
            char_count[char] = char_count.get(char, 0) + 1
            
            while len(char_count) > k:
                left_char = s[left]
                char_count[left_char] -= 1
                if char_count[left_char] == 0:
                    del char_count[left_char]
                left += 1
            
            if len(char_count) == k:
                max_len = max(max_len, right - left + 1)
        
        return max_len

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var longestSubstringWithKUnique = function(s, k) {
    if (k === 0) return 0;
    
    let maxLen = 0;
    let left = 0;
    const charCount = new Map();
    
    for (let right = 0; right < s.length; right++) {
        const char = s[right];
        charCount.set(char, (charCount.get(char) || 0) + 1);
        
        while (charCount.size > k) {
            const leftChar = s[left];
            charCount.set(leftChar, charCount.get(leftChar) - 1);
            if (charCount.get(leftChar) === 0) {
                charCount.delete(leftChar);
            }
            left++;
        }
        
        if (charCount.size === k) {
            maxLen = Math.max(maxLen, right - left + 1);
        }
    }
    
    return maxLen;
};

Asked in Top Tech Interviews

PhonePe

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.