Longest Substring With At Most K Distinct Characters
MediumPractice library · +20 XPstringssliding windowhash map
Given a string S and an integer K, find the length of the longest substring of S that contains at most K distinct characters.
Input
Two lines: The first line contains the string S. The second line contains the integer K.
Output
A single integer representing the length of the longest substring with at most K distinct characters.
Constraints
1 <= |S| <= 200000, 1 <= K <= 26
Time limit 1 s (native code; slower languages get more)Memory 256 MB15 hidden tests
Example 1
Input
araaci 2
Output
4
The longest substring with at most 2 distinct characters is "araa", length 4.
Example 2
Input
eceba 2
Output
3
The longest substring with at most 2 distinct characters is "ece", length 3.
Hints
Similar problems
- Longest Substring Without RepeatsMedium
- String with Most Unique CharactersMedium
- Longest Prefix With No RepeatsMedium
- Longest Subarray with Equal HalvesMedium
- Longest Subarray with At Most K Distinct ElementsMedium
- Distinct Elements in a Sliding WindowMedium
More topics: Strings problems, Hash Map and Hashing problems, Sliding Window problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
araaci 2
Example 2 input
eceba 2