Сформировать минимальное количество палиндромных строк из заданной строки

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

Учитывая строку S , задача состоит в том, чтобы разделить символы S , чтобы сформировать минимальное количество строк-палиндромов.

Примечание: правильных ответов может быть несколько.

Примеры:

Input: S = “geeksforgeeks”
Output: {eegksrskgee, o, f}

Explanation: 
There should be at least 3 strings “eegksrskgee”, “o”, “f”. All 3 formed strings are palindrome.

Input: S = “abbaa”
Output: {“ababa”}

Explanation:
The given string S = “ababa” is already a palindrome string so, only 1 string will be formed.

Input: S = “abc”
Output: {“a”, “b”, “c”}

Explanation: 
There should be at least 3 strings “a”, “b”, “c”. All 3 formed strings are palindrome.

Подход:

Основное наблюдение состоит в том, что строка палиндрома остается неизменной, если ее перевернуть. Длина сформированных строк не имеет значения, поэтому постарайтесь сделать строку как можно большей. Если какой-то символ не может быть частью палиндромной строки, то вставьте этот символ в новую строку.

  • Общий подход заключается в том, чтобы сохранить частоту каждого символа, и если для какого-то символа частота нечетная, мы должны создать новую строку и увеличить наш ответ на 1.
  • Обратите внимание, что если нет символов с нечетной частотой, по крайней мере одна строка все равно нужна, поэтому окончательный ответ будет max(1, символы с нечетной частотой).
  • Чтобы напечатать строку, сохраните нечетные символы частоты символов в векторе и четные символы в другом векторе.
  • Сформируйте одну палиндромную строку со строками, имеющими нечетные символы, и добавьте строку с четным количеством символов, а все остальные строки будут состоять только из одного символа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N*26)

Космическая сложность: O(N)

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