Подстрока называется разнобуквенной, если в ней каждая буква встречается не более чем один раз. Вася любит играть со словами следующим образом. Он берёт обычное слово и находит все его разбиения на подстроки, такие что каждая из них является разнобуквенной. Например, слово «aba» можно разбить на разнобуквенные подстроки тремя способами:
aba
a ba
ab a
Однако у Васи не всегда получается правильно разбить слово. Помогите ему найти все разбиения слова «data» на разнобуквенные подстроки. Подстроки в разбиении не могут быть пустыми. Каждое разбиение записывайте в отдельное поле, добавляя их при необходимости. Подстроки выводите в порядке разбиения, разделяя пробелом. Порядок вывода разбиений
неважен.
Замечание
Подстрока — это последовательность подряд идущих символов, входящих в состав данной строки.
Ответ
1 Ответ
Разнобуквенная подстрока — это строка, в которой все символы уникальны. Мы рассматриваем все возможные способы разбить слово «data» на последовательность таких подстрок. Важно, что подстроки не могут быть пустыми, и порядок подстрок в разбиении имеет значение.
Возможные разбиения:
«data» (целиком)
Проверяем: буквы ‘d’, ‘a’, ‘t’, ‘a’.
Буква ‘a’ встречается дважды ⇒ не подходит.
Разбиения длины 3 + 1:
«dat a»
«dat»: ‘d’, ‘a’, ‘t’ — все буквы уникальны.
«a»: ‘a’ — уникальна.
⇒ подходит.
«da ta»
«da»: ‘d’, ‘a’ — уникальны.
«ta»: ‘t’, ‘a’ — уникальны.
⇒ подходит и т. д.
Итоговые разбиения:
«dat a»
«da ta»
«d a t a»
«d at a»
«da t a»
«d a ta»
Проверка на уникальность:
«dat a» и «d at a» — разные разбиения.
«da ta» и «d a ta» — разные разбиения.
«da t a» и «d a t a» — разные разбиения.
Ответ:
d a t a
da t a
d at a
d a ta
da ta
dat a