Рубрики

Перестановка символов для формирования палиндрома, если это возможно

Для данной строки преобразуйте строку в палиндром без каких-либо изменений, таких как добавление символа, удаление символа, замена символа и т. Д.
Примеры:

Input : "mdaam"
Output : "madam" or "amdma"

Input : "abb"
Output : "bab"

Input : "geeksforgeeks"
Output : "No Palindrome"

1. Подсчитайте вхождения всех персонажей.
2. Подсчитайте нечетные случаи. Если это число больше 1 или равно 1, а длина строки равна даже, то очевидно, что палиндром не может быть сформирован из данной строки.
3. Инициализируйте две пустые строки firstHalf и secondHalf.
4. Пройдите по карте. Для каждого символа со счетчиком в качестве числа присоедините счетчик / 2 символа к концу firstHalf и началу secondHalf.
5. Наконец, верните результат, добавив firstHalf и secondHalf

// Программа CPP для перестановки строки в
// сделать палиндром.
#include <bits/stdc++.h>

using namespace std;

  
string getPalindrome(string str) {

  

  // Сохраняем количество символов

  unordered_map<char, int> hmap;

  for (int i = 0; i < str.length(); i++)

    hmap[str[i]]++;

  

  / * найти количество нечетных элементов.

     Взять на себя) */

  int oddCount = 0;

  char oddChar;

  for (auto x : hmap) {

    if (x.second % 2 != 0) {

      oddCount++;

      oddChar = x.first;

    }

  }

  

  / * odd_cnt = 1 только если длина

     ул нечетный * /

  if (oddCount > 1 || oddCount == 1 && 

                  str.length() % 2 == 0)

    return "NO PALINDROME";

  

  / * Генерируем первую половину палиндрома * /

  string firstHalf = "", secondHalf = "";

  for (auto x : hmap) {

     

    // Построить строку пола (count / 2)

    // вхождения текущего персонажа

    string s(x.second / 2, x.first);

  

    // Прикрепить построенную строку к концу

    // и начало второй половины

    firstHalf = firstHalf + s;

    secondHalf = s + secondHalf;

  }

  

  // Вставляем нечетный символ, если есть

  // любой

  return (oddCount == 1) ? 

         (firstHalf + oddChar + secondHalf) :

         (firstHalf + secondHalf);

}

  

int main() {

  string s = "mdaam";

  cout << getPalindrome(s);

  return 0;

}

Выход:

amdma

Рекомендуемые посты:

Перестановка символов для формирования палиндрома, если это возможно

0.00 (0%) 0 votes