Палиндромные строки длины 3 возможны с использованием символов данной строки
Опубликовано: 22 Сентября, 2022
Для заданной строки S , состоящей из N символов, необходимо вывести все строки-палиндромы длины 3 в лексикографическом порядке, которые можно составить из символов данной строки S .
Примеры:
Input: S = “aabc”
Output:
aba
acaInput: S = “ddadbac”
Output:
aba
aca
ada
dad
dbd
dcd
ddd
Подход: Данную проблему можно решить, используя концепцию хэширования, реализуя ее с использованием карты для хранения количества символов. Выполните следующие шаги, чтобы решить проблему:
- Инициализируйте unordered_map, скажем, Hash , который хранит количество каждого символа.
- Сохраните частоту каждого символа строки в хэше карты.
- Инициализируйте строки Setof, скажем, st , чтобы хранить все палиндромные строки длины 3 .
- Переберите символы [a, z], используя переменную i , и выполните следующие шаги:
- Если значение Hash[i] равно 2 , то перебираем символы в диапазоне [a, z], используя переменную j . Если значение Hash[j] больше 0 и i не равно j , тогда вставьте строку (i + j + i) в Set st .
- В противном случае, если значение Hash[i] больше 2 , выполните итерацию по символам в диапазоне [a, z], используя переменную j , и если значение Hash[j] больше 0 , затем вставьте строку ( i + j + i) в множестве st .
- После выполнения вышеуказанных шагов пройдите по множеству st и напечатайте хранящуюся в нем строку.
Ниже приведена реализация вышеуказанного подхода:
Сложность времени: O(26*26)
Вспомогательное пространство: O(26)