/340. Longest Substring with At Most K Distinct Characters
Previous|Next

340. Longest Substring with At Most K Distinct Characters

Medium
Hash Table49.9% acceptance

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 = abcabcbb, k = 2

Output: 4

Explanation: The longest substring with at most 2 distinct characters is bcbc or cbcb, both of length 4.

Example 2

Input: s = aabbcc, k = 1

Output: 2

Explanation: The longest substring with at most 1 distinct character is aa, bb, or cc, all of length 2.

Example 3

Input: s = abcd, k = 4

Output: 4

Explanation: The entire string abcd has 4 distinct characters, which is equal to k.

Constraints

  • 1 <= len(s) <= 105
  • 1 <= k <= len(s)
  • s consists of English letters (both lowercase and uppercase)
Python (current runtime)

Case 1

Input: s = 'aabacbebebe', k = 3

Expected: 7

Case 2

Input: s = 'zzzzzz', k = 1

Expected: 6

Case 3

Input: s = 'xyzyzyz', k = 2

Expected: 7

Case 4

Input: s = 'abcdef', k = 2

Expected: 2

Case 5

Input: s = 'pqrstuv', k = 3

Expected: 3