Тестовое задание «Найти счастье»

Классная задача с собеседования. Описание довольно длинное, но не поленитесь прочитать и попробовать решить, это будет интересно. Необходимо не только решить задачу, но и сделать это оптимально: на тестовых данных алгоритм должен отрабатывать не дольше 10 секунд. Достаточно интересно посоревноваться с коллегами, кто сделает быстрее и/или оптимальнее.

Описание задачи

Задача: В строке символов найти минимальную по длине подстроку, в которой есть все буквы, необходимые для того, чтобы сложить из них слово «счастье». Если есть несколько вариантов с минимальной длиной, то результатом будет подстрока, расположенная ближе остальных к началу входной строки. Если из символов входной строки слово «счастье» сложить невозможно, результат должен быть равен «Нет счастья».

На регистр букв (строчные/прописные) внимания не обращать. Т.е. подстрока «Есть час» может быть корректным ответом, несмотря на то, что в этой строке прописная «Е».
Английское «c» (си) и русское «с» (эс) считаются разными буквами.

Перевод строки считается одним символом.

Входные данные: строка символов (см. примеры ниже).

Ограничения:

  1. Длина входной строки <= 10000;
  2. Ограничение по времени (ориентировочное) – 10 секунд.

Пример 1

Входные данные:

Собака бывает кусачей
Только от жизни собачьей

Правильный ответ:

сачей
Только от жизни с

Объяснение: из всех подстрок, имеющих как минимум 2 буквы «с», и как минимум по одной букв «ч», «а», «е», «т» и «ь», эта имеет минимальную длину.

Пример 2

Входные данные:

Всё упало, всё пропало

Правильный ответ:

Нет счастья

Объяснение: во входной строке для счастья не хватает букв «е», «т», «ь» и «ч».

Другие примеры

Всего в обработку встроено 5 примеров:

Обработка Найти счастье

Куда вписать алгоритм

Алгоритм вписать в заранее созданную функцию НайтиСчастье(ИсходныеДанные) (расположена в самом начале модуля формы обработки):

Функция НайтиСчастье

Скачать обработку «Найти счастье»

Если и Вам понравилось задание, делитесь впечатлениями и способами реализации.

Оцените статью