Frontend School

Longest Substring with At Most K Distinct Characters

DSA
easy

Longest Substring with At Most K Distinct Characters

Easy
String
Sliding Window
Hash Map

Overview

In many data processing scenarios, such as log analysis or text parsing, it's often useful to identify patterns within a limited scope. This problem asks you to find the longest segment of text that adheres to a specific constraint: containing no more than a certain number of unique character types. This capability is fundamental for tasks like data compression, feature extraction, or even simple text rendering where character set limitations apply.

What you need to do / Task

Given a string s and an integer k, your task is to find the length of the longest substring T of s such that T contains at most k distinct characters.

Input & output

  • Input:
    • s: A string consisting of lowercase English letters.
    • k: An integer representing the maximum number of distinct characters allowed in the substring.
  • Output:
    • An integer representing the length of the longest substring that satisfies the condition.

Clarifications

  • Empty string: If s is empty, the length of the longest substring is 0.
  • k is 0: If k is 0, the only valid substring would be an empty one, so the result should be 0.
  • k is large: If k is greater than or equal to the total number of distinct characters in s, then the entire string s is a valid substring, and its length should be returned.
  • Character set: The string s will only contain lowercase English letters ('a' through 'z').

Examples

1

Example 1

Input:

s = "eceba", k = 2

Output:

3

Note:

The longest substring with at most 2 distinct characters is "ece", which has length 3.

2

Example 2

Input:

s = "aa", k = 1

Output:

2

Note:

The longest substring with at most 1 distinct character is "aa", which has length 2.

3

Example 3

Input:

s = "abaccc", k = 2

Output:

4

Note:

The longest substring with at most 2 distinct characters is "accc", which has length 4.

Constraints

Constraints & assumptions

  • 1 <= s.length <= 5 * 10^4
  • 0 <= k <= 26
  • s consists of lowercase English letters.

Out of scope

  • Handling non-ASCII or Unicode characters.
  • Optimizing for strings with extremely large alphabets (e.g., beyond 26 characters).

What interviewers evaluate

  • Correctly identifying and implementing the sliding window pattern.
  • Efficiently tracking distinct character counts within the window.
  • Demonstrating optimal time complexity (O(N)).
  • Handling edge cases such as empty strings or k=0.

Loading editor...