Палиндромные строки длины 3 возможны с использованием символов данной строки

Опубликовано: 22 Сентября, 2022

Для заданной строки S , состоящей из N символов, необходимо вывести все строки-палиндромы длины 3 в лексикографическом порядке, которые можно составить из символов данной строки S .

Примеры:

Input: S = “aabc”
Output:
aba
aca

Input: 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ