Сделать строку анти-палиндромом

Строка S длины N называется строкой антипалиндрома, если для каждого 0 ≤ i ≤ N-1 S i != S (N — 1 − i). Задача состоит в том, чтобы вывести сформированную Анти-Палиндромную Строку, Если не удается найти, вывести «-1»

Примеры :

• Ввод : S = «abdcccdb»
• Вывод : «cbbaccdd»
• Объяснение : cbbaccdd — это строка анти-палиндрома для каждого 0 ≤ i ≤ N-1, Si != S(N-1−i).
• Вход : s = «xyz»
• Выход : −1

Подход : проблема может быть решена на основе следующей идеи:

Если длина строки S нечетная, тогда ответ всегда будет «-1 », так как условие не выполняется для среднего элемента. Подсчитайте частоту каждого символа в строке S, если частота любого символа больше половины длины строки, то условие также не выполняется. В противном случае напечатайте строку, состоящую из символов непрерывно до их соответствующих частот.

Для реализации идеи выполните следующие шаги:

• Проверьте длинустроки, если она нечетная, выведите «-1 ».
• В противном случае подсчитайтечастоту каждого символа, используя карту.
• Если частота любого символа превышает половину длины строки S, выведите «-1».
• В противном случае напечатайте строку, состоящую из символов непрерывно до их соответствующих частот.

Ниже приведена реализация описанного выше подхода.

С++

// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;

// Function to check whether the string
// can be palindrome or not
string checkPalindrome(string s)
{

    // Size of string
    int n = s.size();

    // If n is odd it is impossible to make
    if (n & 1) {
        return "-1";
    }

    // Declare a Map
    map<char, int> Mp;

    // Count the frequency of each element
    for (int i = 0; i < n; i++)

        Mp[s[i]]++;

    string r = "";

    // Traverse the Map
    for (auto i : Mp) {

        int p = i.second;

        // If max frequency of any character
        // is greater than n/2 then it is
        // impossible to make Anti-palindrome
        if (p > (n / 2)) {
            return "-1";
        }

        // Else make the non-palindrome string
        for (int j = 0; j < p; j++) {

            r += i.first;
        }
    }

    // reverse the string
    reverse(r.begin(), r.begin() + n / 2);

    // return the string
    return r;
}

// Driver Code
int main()
{
    string s = "abdcccdb";

    // Function call
    cout << checkPalindrome(s) << endl;

    return 0;
}

Вывод

cbbaccdd

• Временная сложность : O(N * log N)
• Вспомогательное пространство : O(N)