Ctrl K

Сортировка по кусочкам

Сложная
Даны две строки из цифр одинаковой длины: start и goal. Со строкой start можно сколько угодно раз делать такое действие: выбрать любой непустой кусок из подряд идущих символов и отсортировать цифры в нём по возрастанию, оставив остальную строку как есть. Например, если в 58263 отсортировать кусок 826, получится 52683. Верните True, если из start можно получить goal, и False иначе.
Пример 1
start="5132", goal="1352" → True

Сортируем первые три цифры 513 → 135 и получаем 1352.

Пример 2
start="4401", goal="0441" → True

Сортируем кусок 440 → 044 и получаем 0441.

Пример 3
start="123", goal="132" → False

Сортировка никогда не ставит большую цифру перед меньшей, поэтому 3 не обгонит 2.

Ограничения
  • len(start) == len(goal)
  • 1 ≤ len(start) ≤ 10⁵
  • Обе строки состоят только из цифр
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиОдинаковые буквы на расстоянии СложнаяРазличимые сокращения слов СложнаяНи одной буквы напротив своей копии СложнаяСамое большое число из кусков СредняяБез одинаковых соседей Средняя
загружаем Python…
Вход
start="5132", goal="1352"
Ожидается
True

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 124 теста на сервере, включая скрытые.