Longest Substring with At Most K Distinct Characters
Given a string s and an integer k, find the length of the longest substring that contains at most k distinct characters.
Example
Input: s = eceba, k = 2
Output: 3 (the substring ece)
Approach
Sliding window with a frequency map. Expand right, adding to the map; while the map has more than k distinct keys, shrink from the left, decrementing (and removing when zero) counts.
Input format
Line 1: s
Line 2: k
Not solved yet
Ctrl+Enter
Editor
s = input()
k = int(input())
# TODO: sliding window with a char->count mapfrom collections import defaultdict
counts = defaultdict(int)
left = 0
best = 0
Input (stdin)
Output
Run your code to see output here.
Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.
Editor
s = input()
k = int(input())
# TODO: sliding window with a char->count mapfrom collections import defaultdict
counts = defaultdict(int)
left = 0
best = 0
Input (stdin)
Output
Run your code to see output here.
Isolated sandbox · not executed on your devicePowered by Judge0 CE (free, self-hosted). Runs in an isolated sandbox — not on your device.
