Дана строка s и число k. Найдите длину самой длинной подстроки, в которой не
больше k различных символов. (LeetCode 340 Longest Substring with At Most K
Distinct Characters.)
// LongestKDistinct возвращает длину (в рунах) самой длинной подстроки s,
// содержащей не более k различных символов.
func LongestKDistinct(s string, k int) int
Примеры
"eceba", k=2 → 3 // "ece"
"aa", k=1 → 2
"abc", k=0 → 0
"абвгд", k=10 → 5 // k больше числа различных символов — вся строка
Ограничения
0 ≤ len(s) ≤ 10⁶, 0 ≤ k. Строка в UTF-8, символ — руна; длина считается
в рунах.- Ожидается O(n) в среднем, независимо от
k и размера алфавита.
Устно: как вернуть саму подстроку? Как решать, если строка приходит потоком,
а k маленькое?
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.