Longest Substring with At Most K Distinct Characters - Solution & Explanation

Q: Is Longest Substring with At Most K Distinct Characters easy or hard?

This problem is typically rated Medium because the core idea requires recognizing the sliding window pattern. Once you understand how to maintain constraints while expanding and shrinking the window, the implementation becomes straightforward.

Q: Longest Substring with At Most K Distinct Characters Python/Java solution

Most implementations use a sliding window and a dictionary or HashMap to count characters. The algorithm moves a right pointer across the string, updates counts, and shrinks the left side when distinct characters exceed k. The same logic works across Python, Java, C++, Go, and TypeScript with O(n) time complexity.

Q: How to solve Longest Substring with At Most K Distinct Characters in O(n)?

Use a sliding window with two pointers and a hash map storing character counts. Move the right pointer to expand the window and insert characters into the map. If the number of distinct characters exceeds k, move the left pointer forward and decrease frequencies until the constraint is satisfied again.

Q: What is the best approach for Longest Substring with At Most K Distinct Characters?

The best approach uses a sliding window with a hash table to track character frequencies inside the current window. Two pointers expand and shrink the window while maintaining at most k distinct characters. This method processes each character at most twice and runs in O(n) time with O(k) space.

Q: Is Longest Substring with At Most K Distinct Characters asked at Google/Amazon/Meta?

This problem and its variations appear frequently in interviews at companies like Google, Amazon, and Meta because it tests sliding window reasoning and hash map usage. Many related problems such as longest substring without repeating characters follow the same window pattern.

Q: What data structure is used in Longest Substring with At Most K Distinct Characters?

A hash table (or dictionary) stores the frequency of characters currently inside the sliding window. This allows constant-time updates and quick checks of how many distinct characters are present while expanding or shrinking the window.

Q: What is the time complexity of Longest Substring with At Most K Distinct Characters?

The optimal sliding window solution runs in O(n) time because both pointers move across the string at most once. Each character is added and removed from the hash table at most one time. Space complexity is O(k) since the frequency map stores at most k distinct characters.

MediumPremiumFree on FleetCodeHash Table String Sliding Window7 min readAsked at: Amazon, Microsoft, Apple +9

Practice this problem

Problem Statement

Given a string s and an integer k, return the length of the longest substring of s that contains at most k distinct characters.

Example 1:

Input: s = "eceba", k = 2
Output: 3
Explanation: The substring is "ece" with length 3.

Example 2:

Input: s = "aa", k = 1
Output: 2
Explanation: The substring is "aa" with length 2.

Constraints:

1 <= s.length <= 5 * 10⁴
0 <= k <= 50

Approach Overview

Problem Overview: Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters. The substring must be contiguous, so you need to track a valid window while ensuring the number of unique characters never exceeds k.

Approach 1: Brute Force Enumeration (O(n²) time, O(k) space)

Check every possible substring starting from each index. For a starting index i, expand the substring character by character while tracking distinct characters using a hash map or set. As soon as the number of unique characters exceeds k, stop expanding and move to the next starting index. During expansion, update the maximum substring length seen so far.

This method is straightforward and useful for understanding the constraint: every valid substring must contain at most k unique characters. However, it repeatedly scans overlapping ranges, which leads to O(n²) time in the worst case. Space complexity is O(k) because you store at most k distinct characters in the tracking structure. This approach works for small inputs but does not scale well for long strings.

Approach 2: Sliding Window + Hash Table (O(n) time, O(k) space)

The optimal solution uses the sliding window pattern with two pointers. Maintain a window defined by indices left and right. As you iterate the string with the right pointer, insert each character into a frequency map implemented with a hash table. This map tracks how many times each character appears inside the current window.

If the number of distinct characters becomes greater than k, shrink the window from the left. Decrease the frequency of s[left] in the map, remove it when the count reaches zero, and move the left pointer forward. Continue shrinking until the window again contains at most k distinct characters. At each step, compute the window length right - left + 1 and update the maximum.

Each character enters and leaves the window at most once. That means both pointers traverse the string only once, giving O(n) time complexity. The hash map holds at most k entries, so space complexity is O(k). This pattern appears frequently in string problems involving “longest substring with constraints”.

Recommended for interviews: Interviewers expect the sliding window + hash table solution. The brute force method shows you understand the constraint, but the optimal window approach demonstrates familiarity with two‑pointer techniques and efficient substring processing. Many substring problems reduce to the same pattern: expand the window to include characters, then contract it when constraints are violated.

Solution

We can use the idea of a sliding window, with a hash table cnt to record the occurrence count of each character within the window, and l to denote the left boundary of the window.

Iterate through the string, adding the character at the right boundary to the hash table each time. If the number of distinct characters in the hash table exceeds k, remove the character at the left boundary from the hash table, then update the left boundary l.

Finally, return the length of the string minus the length of the left boundary.

The time complexity is O(n), and the space complexity is O(k). Here, n is the length of the string.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

Approach	Time	Space	When to Use
Brute Force Enumeration with Hash Set	O(n²)	O(k)	Useful for understanding the constraint and validating logic on small inputs
Sliding Window + Hash Table	O(n)	O(k)	Optimal approach for large strings and the standard interview solution

Video Solution

L6. Longest Substring With At Most K Distinct Characters | 2 Pointers and Sliding Window Playlist • take U forward • 230,992 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Longest Substring with At Most K Distinct Characters easy or hard?

This problem is typically rated Medium because the core idea requires recognizing the sliding window pattern. Once you understand how to maintain constraints while expanding and shrinking the window, the implementation becomes straightforward.

Longest Substring with At Most K Distinct Characters Python/Java solution

Most implementations use a sliding window and a dictionary or HashMap to count characters. The algorithm moves a right pointer across the string, updates counts, and shrinks the left side when distinct characters exceed k. The same logic works across Python, Java, C++, Go, and TypeScript with O(n) time complexity.

How to solve Longest Substring with At Most K Distinct Characters in O(n)?

Use a sliding window with two pointers and a hash map storing character counts. Move the right pointer to expand the window and insert characters into the map. If the number of distinct characters exceeds k, move the left pointer forward and decrease frequencies until the constraint is satisfied again.

What is the best approach for Longest Substring with At Most K Distinct Characters?

The best approach uses a sliding window with a hash table to track character frequencies inside the current window. Two pointers expand and shrink the window while maintaining at most k distinct characters. This method processes each character at most twice and runs in O(n) time with O(k) space.

Is Longest Substring with At Most K Distinct Characters asked at Google/Amazon/Meta?

This problem and its variations appear frequently in interviews at companies like Google, Amazon, and Meta because it tests sliding window reasoning and hash map usage. Many related problems such as longest substring without repeating characters follow the same window pattern.

What data structure is used in Longest Substring with At Most K Distinct Characters?

A hash table (or dictionary) stores the frequency of characters currently inside the sliding window. This allows constant-time updates and quick checks of how many distinct characters are present while expanding or shrinking the window.

What is the time complexity of Longest Substring with At Most K Distinct Characters?

The optimal sliding window solution runs in O(n) time because both pointers move across the string at most once. Each character is added and removed from the hash table at most one time. Space complexity is O(k) since the frequency map stores at most k distinct characters.

Ready to solve this problem?

Practice Longest Substring with At Most K Distinct Characters with our built-in code editor and test cases.

Practice on FleetCode

Longest Repeating Character Replacement

Longest Substring with At Most Two Distinct Characters

Problem Info

DifficultyMedium

Acceptance49.9%

Approaches1

Reading time7 min

Asked at

Amazon Microsoft Apple Goldman Sachs Meta