C++ 找出使用给定字符串字符的两个唯一回文字符串

在这个问题中，我们将使用给定字符串的字符构造两个回文字符串。

我们可以使用字符的频率来解决这个问题。只有当两个字符的频率都是偶数，或者某些字符的频率是偶数而其他字符的频率是奇数时，我们才能构造出两个新的回文字符串。

问题描述 - 我们有一个包含两个不同字符的字符串alpha，大小为N。我们需要使用alpha的字符构造两个回文字符串，这些回文字符串与给定的字符串alpha不相同。

示例

在给定大小的每个前缀的每个字符递增后，结果字符串为’gffe’。

输入

alpha = "aaabbabbabb"

输出

bbbaaaaabbb, aabbbabbbaa

解释

‘bbbaaaaabbb’和‘aabbbabbbaa’是我们从给定的字符串构造的不同回文字符串。

输入

alpha = "aabbb"

输出

abbba, babab

输入

alpha = "aaabbabbabb"

输出

bbbaaaaabbb, aabbbabbbaa

解释

两个输出字符串都是由给定字符的字符串构建成的新的回文串。

输入

alpha = "aaabbb";

输出

‘Not possible.’

解释

无法从给定字符串构建两个不同的回文字符串。

方法1

如果两个字符的频率都是奇数，就无法构建两个新的回文字符串。例如，在字符串’aaabbb’中，’a’和’b’都出现了3次。因此，我们无法构建任何单个的回文字符串。

如果任何单个字符的频率是偶数，我们总是可以构建两个不同的回文字符串。

• 对于偶-奇字符频率: 从’aabbb’中，我们可以构建’abbba’和’babab’字符串。

• 对于偶-偶字符频率：从’aabb’中，我们可以构建’abba’和’baab’类型的字符串。

算法

• 步骤 1 − 定义 ‘freq’映射以存储字符的频率，并遍历字符串以计算每个字符的频率。

• 步骤 2 − 定义 ‘temp1’ 和 ‘temp2’ 存储两个字符，并定义 ‘freq1’ 和 ‘freq2’ 变量存储每个字符的频率。

• 步骤 3 − 遍历映射，如果 flag 1，则将键赋给 ‘temp1’，将值赋给 ‘freq1’。同时，初始化 ‘temp2’ 和 ‘freq2’ 字符。

• 步骤 4 − 如果 ‘freq1’ 和 ‘freq2’ 都是1或奇数，则打印 ‘not possible’，因为我们无法使用字符串字符构建两个回文字符串。

• 步骤 5 − 如果 ‘freq1’ 和 ‘freq2’ 都是偶数，则按照以下步骤进行。

• 步骤 5.1 − 我们需要打印第一个回文字符串。因此，打印 ‘temp1’ 字符 ‘freq1/2’ 次，打印 ‘temp2’ 字符 ‘freq2’ 次，然后再次打印 ‘temp1’ 字符 ‘freq1/2’ 次。

• 步骤 5.2 − 对于第二个字符串，打印 ‘temp2’ 字符 ‘freq2/2’ 次，打印 ‘temp1’ 字符 ‘freq1’ 次，然后再次打印 ‘temp2’ 字符 ‘freq2/2’ 次。

• 步骤 6 − 如果 freq1 和 freq2 中有一个是奇数，则按照以下步骤进行。

• 步骤 6.1 − 对于第一个字符串，如果 freq1 是偶数，则打印 ‘temp1’ 字符 ‘freq1/2’ 次，打印 ‘temp2’ 字符 ‘freq2’ 次，然后打印 ‘temp1’ 字符 ‘freq2/2’ 次。否则，如果 freq2 是偶数，则打印 ‘temp2’ 字符 ‘freq2/2’ 次，打印 ‘temp1’ 字符 ‘freq1’ 次，然后打印 ‘temp2’ 字符 ‘freq1/2’ 次。

• 步骤 6.2 − 对于第二个字符串，如果 freq1 是偶数，则打印 ‘temp2’ 字符 ‘freq2/2’ 次，打印 ‘temp1’ 字符 ‘freq1/2’ 次，单个 ‘temp2’ 字符放在字符串中间，然后打印 freq1/2 个 ‘temp1’ 字符和 freq2/2 个 ‘temp2’ 字符。

• 步骤 6.3 − 否则，如果 freq1 是奇数，则打印 ‘temp1’ 字符 ‘freq2/2’ 次，打印 ‘temp2’ 字符 ‘freq2/2’ 次，单个 ‘temp1’ 字符放在字符串中间，然后打印 freq2/2 个 ‘temp2’ 字符和 freq1/2 个 ‘temp1’ 字符。

示例

#include <bits/stdc++.h>
using namespace std;
void find2Palindromes(string alpha) {
   // To store the frequency of characters
   map<char, int> freq;

   // Calculating the frequency of each character
   for (int p = 0; p < alpha.size(); p++) {
      freq[alpha[p]] += 1;
   }
   char temp1 = ' ', temp2 = ' ';
   int fre1 = 0, freq2 = 0;
   int flag = 1;

   // Traverse the map
   for (auto ch : freq) {

      // Get the frequency of the first character
      if (flag == 1) {
         temp1 = ch.first;
         fre1 = ch.second;
         flag++;
      }
      // Get the frequency of the second character
      else {
         temp2 = ch.first;
         freq2 = ch.second;
      }
   }
   // Check whether two palindrome strings are possible
   if ((fre1 == 1 || freq2 == 1) || (fre1 % 2 == 1) && (freq2 % 2 == 1)) {
      cout << "not possible";
      cout << endl;
   }

   // Case 1 - Both are even
   else if (fre1 % 2 == 0 && freq2 % 2 == 0) {
      // Print half temp1
      for (int p = 1; p <= fre1 / 2; p++)
      cout << temp1;

      // Print temp2
      for (int p = 1; p <= freq2; p++)
      cout << temp2;

      // Print half temp1
      for (int p = 1; p <= fre1 / 2; p++)
      cout << temp1;
      cout << " ";

      // Second palindrome string
      for (int p = 1; p <= freq2 / 2; p++)
         cout << temp2;
      for (int p = 1; p <= fre1; p++)
         cout << temp1;
      for (int p = 1; p <= freq2 / 2; p++)
         cout << temp2;
   }

   // Case 2 - One is even, and one is odd
   else if (fre1 % 2 != 0 || freq2 % 2 != 0) {

      // Print the first string
      if (fre1 % 2 == 0) {
         for (int p = 1; p <= fre1 / 2; p++)
            cout << temp1;
         for (int p = 1; p <= freq2; p++)
            cout << temp2;
         for (int p = 1; p <= fre1 / 2; p++)
            cout << temp1;
         cout << " ";
      } else {
         for (int p = 1; p <= freq2 / 2; p++)
            cout << temp2;
         for (int p = 1; p <= fre1; p++)
            cout << temp1;
         for (int p = 1; p <= freq2 / 2; p++)
            cout << temp2;
         cout << " ";
      }

      // Print the second string
      if (fre1 % 2 == 0) {
         for (int p = 1; p <= freq2 / 2; p++)
            cout << temp2;
         for (int p = 1; p <= fre1 / 2; p++)
            cout << temp1;
         cout << temp2;
         for (int p = 1; p <= fre1 / 2; p++)
            cout << temp1;
         for (int p = 1; p <= freq2 / 2; p++)
         cout << temp2;
      } else {
         for (int p = 1; p <= fre1 / 2; p++)
            cout << temp1;
         for (int p = 1; p <= freq2 / 2; p++)
            cout << temp2;
         cout << temp1;
         for (int p = 1; p <= freq2 / 2; p++)
            cout << temp2;
         for (int p = 1; p <= fre1 / 2; p++)
            cout << temp1;
      }
   }
}
int main() {
   string alpha = "aaabbabbabb";
   cout << "The original String is - " << alpha << endl << "Palindrome Strings are - ";
   find2Palindromes(alpha);
}

输出结果

The original String is - aaabbabbabb
Palindrome Strings are - bbbaaaaabbb aabbbabbbaa

时间复杂度 – O（N）用于多次遍历字符串。

空间复杂度 – O（1）因为我们在不使用额外空间的情况下打印回文字符串。

我们可以通过将第一个字符放在第一个字符串的中间，将第二个字符放在第二个字符串的中间，从给定的字符串中创建两个不同的回文字符串。

程序员可以用substr（）方法替换for循环来缩短代码。首先，我们可以使用包含freq1次temp1字符和freq2次temp2字符的String构造函数创建一个字符串。然后，在我们需要的时候，我们可以从两个字符串中提取特定长度的子字符串。