TGViewer
Алгоритмы - Собеседования, Олимпиады, ШАД Алгоритмы - Собеседования, Олимпиады, ШАД @algoses · 12.1K subscribers
Post #305 6.96K
Задача с собеседования в Яндекс

Дан некоторый алфавит и строка. Необходимо найти в строке панграмму минимальной длины, где панграмма - это такая подстрока исходной строки, в которую входят все буквы из алфавита (но необязательно только они).

Пример:
A = {a, b, c}
s = "dfagabkaceb"
Ответом могут быть строки "bkac" и "aceb"

Решение:
Халявные два указателя буквально подарят тебе оффер
Будем двигать правый указатель, расширяя подстроку, пока не включим все символы из алфавита. Как только все символы оказались в окне, будем двигать левый указатель, обновляя ответ и сохраняя все необходимые символы.
Обязательно надо проверить, что панграмма с концом в конце исходной строки также рассматривается.
Асимптотика O(N)

В целом, можно предложить алгоритм без сдвига начала строки за O(NS), что тоже прокатит
Типичные ошибки:
1) Не обработать ненахождение панграммы в принципе
2) Неправильно похендлить алфавит длиной один
3) Ненахождение ответа в конце текста


@algoses
  • 👍 17
  • ❤ 4
  • 👏 1
  • 💊 1
More from @algoses
  1. Sep 27, 2026Ты поступишь в ШАД Старт набора на наши ШАДовские курсы: без воды и лишней теории, 3 месяц…
  2. Sep 26, 2026Задача с собеседования в Zoho Даны две строки: s и goal. Верните true, если можно поменять…
  3. Sep 25, 2026Как залететь в хфт и стать миллионером, залутать сочную зумершку? Обсудим в новом ролике.…
  4. Sep 23, 2026Задача с собеседования в Zoho Даны две строки s и t. Определите, являются ли они изоморфны…
  5. Sep 19, 2026Полный цикл отбора в Spectral на SWE (HFT) Недавно рассказывали про отбор в Fast Forward н…
  6. Sep 18, 2026❗️ Яндекс открыл Intern Week Offer на стажировку, где всего за неделю ты можешь получить о…
Threads Profile ViewerView any public Threads profile without an account.Open ThreadLook →Writing with AI? Make it sound human.Metric37 rewrites AI drafts so they read naturally. Free AI detector, 1,500 words free.Try Metric37 →