Классная задача с собеседования. Описание довольно длинное, но не поленитесь прочитать и попробовать решить, это будет интересно. Необходимо не только решить задачу, но и сделать это оптимально: на тестовых данных алгоритм должен отрабатывать не дольше 10 секунд. Достаточно интересно посоревноваться с коллегами, кто сделает быстрее и/или оптимальнее.
Описание задачи
Задача: В строке символов найти минимальную по длине подстроку, в которой есть все буквы, необходимые для того, чтобы сложить из них слово «счастье». Если есть несколько вариантов с минимальной длиной, то результатом будет подстрока, расположенная ближе остальных к началу входной строки. Если из символов входной строки слово «счастье» сложить невозможно, результат должен быть равен «Нет счастья».
На регистр букв (строчные/прописные) внимания не обращать. Т.е. подстрока «Есть час» может быть корректным ответом, несмотря на то, что в этой строке прописная «Е».
Английское «c» (си) и русское «с» (эс) считаются разными буквами.
Перевод строки считается одним символом.
Входные данные: строка символов (см. примеры ниже).
Ограничения:
- Длина входной строки <= 10000;
- Ограничение по времени (ориентировочное) – 10 секунд.
Пример 1
Входные данные:
Собака бывает кусачей
Только от жизни собачьей
Правильный ответ:
сачей
Только от жизни с
Объяснение: из всех подстрок, имеющих как минимум 2 буквы «с», и как минимум по одной букв «ч», «а», «е», «т» и «ь», эта имеет минимальную длину.
Пример 2
Входные данные:
Всё упало, всё пропало
Правильный ответ:
Нет счастья
Объяснение: во входной строке для счастья не хватает букв «е», «т», «ь» и «ч».
Другие примеры
Всего в обработку встроено 5 примеров:
Куда вписать алгоритм
Алгоритм вписать в заранее созданную функцию НайтиСчастье(ИсходныеДанные) (расположена в самом начале модуля формы обработки):
Скачать обработку «Найти счастье»
Если и Вам понравилось задание, делитесь впечатлениями и способами реализации.