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.

Description Solution Video 21:32

340. Longest Substring with At Most K Distinct Characters

Medium49.9% acceptance12 companiesPremium elsewhere, free here

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

Asked at 12 companies

Coupang Appdynamics Yandex BitGo Tiktok Oracle Apple

Google Amazon Microsoft Goldman Sachs Meta

Topics

21:32

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

340. Longest Substring with At Most K Distinct Characters

Asked at 12 companies

Topics

Similar problems