Дан алфавит и строка. Найдите в строке панграмму минимальной длины —
кратчайшую подстроку, в которой встречаются все буквы алфавита (другие символы
в ней тоже могут быть). Это вариация LeetCode 76 Minimum Window Substring.
// MinPangram возвращает кратчайшую подстроку s, содержащую все символы alphabet.
// Если такой нет — "".
func MinPangram(s string, alphabet []rune) string
Пример
alphabet = {x, y, z}, s = "pqxrxysxzty" → "ysxz" или "xzty"
Обе подстроки длины 4 подходят — вернуть можно любую из них.
Требования
- Если подходящих подстрок минимальной длины несколько, верните любую.
- Алфавит может содержать повторы — это одно и то же множество букв. Пустой
алфавит — ответ
"".
- Строка в UTF-8, символ — руна, длина считается в рунах.
0 ≤ len(s) ≤ 10⁶, размер алфавита до 10⁵. Ожидается O(n + |alphabet|)
в среднем — независимо от размера алфавита.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.