Show problems as
Classic problem #340MediumHash TableStringSliding Window

Longest Substring with At Most K Distinct Characters

Real-world version: Longest Belt Run Within a Colour Budget
Tracked in this browser only
Read Longest Substring with At Most K Distinct Characters on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

Learn the pattern firstSliding Window · Strings, animated step by step

Parts travel down a belt in a fixed order, and each part carries a single-character colour code. The string s lists those codes from the first part to the last.

A packing cell can handle a stretch of consecutive parts only while that stretch uses at most k different colour codes. Return the number of parts in the longest such stretch. When k is 0 no stretch qualifies, so the answer is 0.

Examples

Example 1

Input
s = "abaccc", k = 2
Output
4

The four parts from position 2 to position 5 carry the codes a, c, c, c, which is two different codes and so within the budget of two.

Example 2

Input
s = "xyxyzz", k = 1
Output
2

With a budget of one code, a stretch may only hold repeats of a single code. The two parts at positions 4 and 5 both carry z, giving a run of two.

Example 3

Input
s = "abcdef", k = 0
Output
0

A budget of zero codes admits no part at all, so the answer is 0.

Constraints

  • 1 <= s.length <= 5 * 10^4
  • 0 <= k <= 50
  • s contains only lowercase English letters and digits.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def length_of_longest_substring_k_distinct(s: str, k: int) -> int:
Java
public int lengthOfLongestSubstringKDistinct(String s, int k)

More on the same topics