使用给定字符串的字符找到两个唯一的回文字符串

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

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

问题陈述 - 我们给定一个包含两个不同字符且大小等于 N 的字符串 alpha。我们需要使用 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 或奇数，则打印“不可能”，因为我们无法使用字符串字符构建两个回文字符串。
步骤 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 字符。

示例

以下是上述算法的程序 -

C C++ Java Python

#include <stdio.h>
#include <string.h>

// Function to find and print two palindrome strings
void find2Palindromes(const char* alpha) {
   // To store the frequency of characters
   int freq[256] = {0};

   // Calculating the frequency of each character
   for (int p = 0; alpha[p] != '\0'; p++) {
      freq[(int)alpha[p]] += 1;
   }

   char temp1 = ' ', temp2 = ' ';
   int freq1 = 0, freq2 = 0;
   int flag = 1;

   // Traverse the frequency array
   for (int i = 0; i < 256; i++) {
      if (freq[i] > 0) {
         // Get the frequency of the first character
         if (flag == 1) {
            temp1 = (char)i;
            freq1 = freq[i];
            flag++;
         }
         // Get the frequency of the second character
         else {
            temp2 = (char)i;
            freq2 = freq[i];
         }
      }
   }

   // Check whether two palindrome strings are possible
   if ((freq1 == 1 || freq2 == 1) || (freq1 % 2 == 1 && freq2 % 2 == 1)) {
      printf("not possible\n");
   }
   // Case 1 - Both are even
   else if (freq1 % 2 == 0 && freq2 % 2 == 0) {
      // Print half temp1
      for (int p = 1; p <= freq1 / 2; p++)
         printf("%c", temp1);

      // Print temp2
      for (int p = 1; p <= freq2; p++)
         printf("%c", temp2);

      // Print half temp1
      for (int p = 1; p <= freq1 / 2; p++)
         printf("%c", temp1);
      printf(" ");

      // Second palindrome string
      for (int p = 1; p <= freq2 / 2; p++)
         printf("%c", temp2);
      for (int p = 1; p <= freq1; p++)
         printf("%c", temp1);
      for (int p = 1; p <= freq2 / 2; p++)
         printf("%c", temp2);
   }
   // Case 2 - One is even, and one is odd
   else if (freq1 % 2 != 0 || freq2 % 2 != 0) {
      // Print the first string
      if (freq1 % 2 == 0) {
         for (int p = 1; p <= freq1 / 2; p++)
            printf("%c", temp1);
         for (int p = 1; p <= freq2; p++)
            printf("%c", temp2);
         for (int p = 1; p <= freq1 / 2; p++)
            printf("%c", temp1);
         printf(" ");
      } else {
         for (int p = 1; p <= freq2 / 2; p++)
            printf("%c", temp2);
         for (int p = 1; p <= freq1; p++)
            printf("%c", temp1);
         for (int p = 1; p <= freq2 / 2; p++)
            printf("%c", temp2);
         printf(" ");
      }

      // Print the second string
      if (freq1 % 2 == 0) {
         for (int p = 1; p <= freq2 / 2; p++)
            printf("%c", temp2);
         for (int p = 1; p <= freq1 / 2; p++)
            printf("%c", temp1);
         printf("%c", temp2);
         for (int p = 1; p <= freq1 / 2; p++)
            printf("%c", temp1);
         for (int p = 1; p <= freq2 / 2; p++)
            printf("%c", temp2);
      } else {
         for (int p = 1; p <= freq1 / 2; p++)
            printf("%c", temp1);
         for (int p = 1; p <= freq2 / 2; p++)
            printf("%c", temp2);
         printf("%c", temp1);
         for (int p = 1; p <= freq2 / 2; p++)
            printf("%c", temp2);
         for (int p = 1; p <= freq1 / 2; p++)
            printf("%c", temp1);
      }
   }
}

int main() {
   const char* alpha = "aaabbabbabb";
   printf("The original String is - %s\nPalindrome Strings are - ", alpha);
   find2Palindromes(alpha);
   return 0;
}

输出

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

#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

import java.util.HashMap;
import java.util.Map;

public class PalindromeStrings {
   public static void find2Palindromes(String alpha) {
      // To store the frequency of characters
      Map<Character, Integer> freq = new HashMap<>();

      // Calculating the frequency of each character
      for (char c : alpha.toCharArray()) {
         freq.put(c, freq.getOrDefault(c, 0) + 1);
      }

      char temp1 = ' ', temp2 = ' ';
      int freq1 = 0, freq2 = 0;
      int flag = 1;

      // Traverse the map
      for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
         // Get the frequency of the first character
         if (flag == 1) {
            temp1 = entry.getKey();
            freq1 = entry.getValue();
            flag++;
         }
         // Get the frequency of the second character
         else {
            temp2 = entry.getKey();
            freq2 = entry.getValue();
         }
      }

      // Check whether two palindrome strings are possible
      if ((freq1 == 1 || freq2 == 1) || (freq1 % 2 == 1 && freq2 % 2 == 1)) {
         System.out.println("not possible");
      }
      // Case 1 - Both are even
      else if (freq1 % 2 == 0 && freq2 % 2 == 0) {
         // Print half temp1
         for (int p = 1; p <= freq1 / 2; p++) {
            System.out.print(temp1);
         }
         // Print temp2
         for (int p = 1; p <= freq2; p++) {
            System.out.print(temp2);
         }
         // Print half temp1
         for (int p = 1; p <= freq1 / 2; p++) {
            System.out.print(temp1);
         }
         System.out.print(" ");

         // Second palindrome string
         for (int p = 1; p <= freq2 / 2; p++) {
            System.out.print(temp2);
         }
         for (int p = 1; p <= freq1; p++) {
            System.out.print(temp1);
         }
         for (int p = 1; p <= freq2 / 2; p++) {
             System.out.print(temp2);
         }
      }
      // Case 2 - One is even, and one is odd
      else {
         // Print the first string
         if (freq1 % 2 == 0) {
            for (int p = 1; p <= freq1 / 2; p++) {
               System.out.print(temp1);
            }
            for (int p = 1; p <= freq2; p++) {
               System.out.print(temp2);
            }
            for (int p = 1; p <= freq1 / 2; p++) {
               System.out.print(temp1);
            }
            System.out.print(" ");
         } else {
            for (int p = 1; p <= freq2 / 2; p++) {
               System.out.print(temp2);
            }
            for (int p = 1; p <= freq1; p++) {
               System.out.print(temp1);
            }
            for (int p = 1; p <= freq2 / 2; p++) {
               System.out.print(temp2);
            }
            System.out.print(" ");
         }

         // Print the second string
         if (freq1 % 2 == 0) {
            for (int p = 1; p <= freq2 / 2; p++) {
               System.out.print(temp2);
            }
            for (int p = 1; p <= freq1 / 2; p++) {
               System.out.print(temp1);
            }
            System.out.print(temp2);
            for (int p = 1; p <= freq1 / 2; p++) {
               System.out.print(temp1);
            }
            for (int p = 1; p <= freq2 / 2; p++) {
               System.out.print(temp2);
            }
         } else {
            for (int p = 1; p <= freq1 / 2; p++) {
               System.out.print(temp1);
            }
            for (int p = 1; p <= freq2 / 2; p++) {
               System.out.print(temp2);
            }
            System.out.print(temp1);
            for (int p = 1; p <= freq2 / 2; p++) {
               System.out.print(temp2);
            }
            for (int p = 1; p <= freq1 / 2; p++) {
               System.out.print(temp1);
            }
         }
      }
   }

   public static void main(String[] args) {
      String alpha = "aaabbabbabb";
      System.out.println("The original String is - " + alpha);
      System.out.print("Palindrome Strings are - ");
      find2Palindromes(alpha);
   }
}

输出

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

def find_2_palindromes(alpha):
   # To store the frequency of characters
   freq = {}

   # Calculating the frequency of each character
   for char in alpha:
      freq[char] = freq.get(char, 0) + 1

   temp1, temp2 = ' ', ' '
   freq1, freq2 = 0, 0
   flag = 1

   # Traverse the dictionary
   for char, count in freq.items():
      # Get the frequency of the first character
      if flag == 1:
         temp1 = char
         freq1 = count
         flag += 1
      # Get the frequency of the second character
      else:
         temp2 = char
         freq2 = count

   # Check whether two palindrome strings are possible
   if freq1 == 1 or freq2 == 1 or (freq1 % 2 == 1 and freq2 % 2 == 1):
      print("not possible")
   else:
      # Case 1 - Both are even
      if freq1 % 2 == 0 and freq2 % 2 == 0:
         # Print half temp1
         print(temp1 * (freq1 // 2), end='')

         # Print temp2
         print(temp2 * freq2, end='')

         # Print half temp1
         print(temp1 * (freq1 // 2), end=' ')
          
         # Second palindrome string
         print(temp2 * (freq2 // 2), end='')
         print(temp1 * freq1, end='')
         print(temp2 * (freq2 // 2))
      else:
         # Print the first string
         if freq1 % 2 == 0:
            print(temp1 * (freq1 // 2), end='')
            print(temp2 * freq2, end='')
            print(temp1 * (freq1 // 2), end=' ')
         else:
            print(temp2 * (freq2 // 2), end='')
            print(temp1 * freq1, end='')
            print(temp2 * (freq2 // 2), end=' ')
          
         # Print the second string
         if freq1 % 2 == 0:
            print(temp2 * (freq2 // 2), end='')
            print(temp1 * (freq1 // 2), end='')
            print(temp2, end='')
            print(temp1 * (freq1 // 2), end='')
            print(temp2 * (freq2 // 2))
         else:
            print(temp1 * (freq1 // 2), end='')
            print(temp2 * (freq2 // 2), end='')
            print(temp1, end='')
            print(temp2 * (freq2 // 2), end='')
            print(temp1 * (freq1 // 2))

# Main function
if __name__ == "__main__":
   alpha = "aaabbabbabb"
   print("The original String is -", alpha)
   print("Palindrome Strings are -", end=' ')
   find_2_palindromes(alpha)

输出

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

时间复杂度 - O(N)，因为多次遍历字符串。

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

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

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

Shubham Vora

更新于: 2023年10月20日

115 次查看

开启您的职业生涯

通过完成课程获得认证

开始学习

使用给定字符串的字符找到两个唯一的回文字符串

示例

解释

解释

解释

方法 1

算法

示例

输出

输出

输出

输出

开启您的 职业生涯

开启您的职业生涯