使用給定字串的字元找到兩個唯一的迴文字串

在這個問題中，我們將使用給定字串的字元構建兩個迴文字串。

我們可以使用字元的頻率來解決這個問題。只有當兩個字元的頻率都為偶數，或者任何字元具有偶數頻率而其他字元具有奇數頻率時，我們才能構建兩個新的迴文字串。

問題陳述 - 我們給定一個包含兩個不同字元且大小等於 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

演算法

示例

輸出

輸出

輸出

輸出

開啟您的 職業生涯

開啟您的職業生涯