Checks whether a string can form a palindrome string by swapping character pairs at indices with unequal characters in a binary string

Problem Statement

We have a string str and a binary string B. The length of both strings is equal to N. We need to check if we can make string str a palindrome string by swapping its characters multiple times on any pair of indexes containing unequal characters in string B.

ExampleExample

enter

str = ‘AAS’ B = ‘101’

Output

‘YES’

The Chinese translation of

Explanation

is:

Explanation

We can exchange str[1] and str[2] because B[1] and B[2] are not equal. The final string can be 'ASA'.

enter

str = ‘AASS’ B = ‘1111’

Output

‘No’

The Chinese translation of

Explanation

is:

Explanation

We cannot make the string palindrome because string B does not contain unequal characters.

enter

str = ‘AASSBV’ B = ‘111100’

Output

‘No’

The Chinese translation of

Explanation

is:

Explanation

We cannot make the string str a palindrome due to character frequency mismatch.

method one

In the first method, we will check if any palindrome string can be created using all the characters of the string str. If so, we can check if we can swap the characters in the index pairs containing unequal characters in string B and make the string a palindrome. Otherwise, we return false.

algorithm

• Step 1 - Execute the utility() function and exchange characters according to the given conditions to determine whether the string can become a palindrome by exchanging characters.

• Step 2 - Define canBePalindromic() function to check if we can construct any palindrome string using the characters of str.

• Step 2.1 − Create a map that stores each character in the string str and its frequency. Use a for loop to iterate through the string and count the frequency of characters.

• Step 2.2 - Count the number of characters with even and odd frequencies.

• Step 2.3 - Use set to get the total number of unique characters in a string.

• Step 2.4 − Returns true if the string length is odd and contains only one character with odd frequency.

• Step 2.5 − If the string length is even, then all characters with even frequency, and 0 characters with odd frequency, return true.

• Step 2.6 − Return false.

• Step 3 - If the string cannot become a palindrome, return false.

• Step 4 - If string B contains multiple '1's and '0's, return true; otherwise, return false.

Example

#include <bits/stdc++.h>
using namespace std;
// function to check if the string can be palindromic
bool canBePalindromic(string str){
   //Creating the map to store the frequency of each character
   map<char, int> charMap;
   // store the frequency of each character of string Str
   for (int i = 0; i < str.length(); i++) {
      charMap[str[i]] += 1;
   }
   // to store the count of even and odd frequent characters
   int even = 0, odd = 0;
   // iterate through the map
   for (auto e : charMap)  {
      //If frequency is odd, increment odd count; else, increment even count
      if (e.second % 2 == 1) {
         odd++;
      } else {
         even++;
      }
   }
   // set to store unique characters of string Str
   unordered_set<char> set;
   //Insert all characters of string Str in set
   for (int i = 0; i < str.size(); i++){
      set.insert(str[i]);
   }
   // if the string length is odd and only one character has an odd frequency, return true
   if (str.size() % 2 == 1 && even == set.size() - 1 && odd == 1){
      return true;
   }
   // If the string length is even and all characters have even frequency, return true
   if (str.size() % 2 == 0 && even == set.size() && odd == 0){
      return true;
   }
   // else return false
   return false;
}
// function to check if the string can be palindromic by swapping characters according to string B
bool utility(string S, string B){
   // If string S cannot be palindromic, return false.
   if (canBePalindromic(S) == false){
      return false;
   } else{
      // if at least one '1' and '0' is present in string B, string S can be palindromic
      int one = 0, zero = 0;
      for (int i = 0; i < B.size(); i++) {
         // If the current character is '0.'
         if (B[i] == '0'){
            zero++;
         } else {
            one++;
         }
      }
      // return true if at least one '1' and '0' is present in the string B
      if (one >= 1 && zero >= 1){
         return true;
      } else {
         return false;
      }
   }
}
int main(){
   string S = "NANA";
   string B = "0001";
   bool result = utility(S, B);
   if (result)
      cout << "Yes";
   else
      cout << "No";
   return 0;
}

Output

Yes

• Time complexity - O(NlogN), because we use a for loop to traverse the string, and the insert() method of set takes (logN) time.

• Space Complexity - O(K), where K is the total number of unique characters.

Method Two

In this method, we will use an array to store the frequency of characters instead of using a map.

algorithm

• Step 1 - Create a 'charFrequancy' array of length 26 and initialize it to zero.

• Step 2 - Count the total number of 1's and 0's in string B.

• Step 3 - Update the frequency of each character in the array.

• Step 4 - If the string length is even and the odd frequency is not zero, return false.

• Step 5 - If the string length is odd and the odd frequency is greater than 1, return false.

• Step 6 - Returns true if both 1 and 0 exist in the string.

• Step 7 - Return false.

Example

#include <bits/stdc++.h>
using namespace std;
// function to check if the given string can be converted to a palindrome
bool utility(string str, string B){
   // array to store character counts in str
   int charFrequancy[26] = {0};
   int ones = 0, zeros = 0, odd_fre = 0;
   // count ones and zeros
   for (char ch : B) {
      if (ch == '1')
         ones++;
      if (ch == '0')
         zeros++;
   }
   // store counts of characters
   for (char ch : str){
      charFrequancy[ch - 'A']++;
   }
   // check total character with odd frequency
   for (int i = 0; i < 26; i++){
      if (charFrequancy[i] % 2 == 1)
         odd_fre++;
   }
   if (str.length() % 2 == 0 && odd_fre != 0)
      return false;
   if (str.length() % 2 == 1 && odd_fre > 1)
      return false;
   if (ones > 0 && zeros > 0)
      return true;
   return false;
}
int main(){
   string S = "NBCNB";
   string B = "01010";
   if (utility(S, B)){
      cout << "Yes";
   } else {
      cout << "No";
   }
   return 0;
}

Output

Yes

• Time complexity - O(N) because we use a for loop to iterate over the string.

• Space Complexity − O(1) since we always use an array of length 26.

in conclusion

We learned two methods to check if a string can become a palindrome by swapping characters based on a given condition. The first method uses collections and maps, while the second method only uses arrays to store data. The second method is better than the first method because the insert() method takes O(logn) time to insert data into the collection, while the array only takes O(1) time.

The above is the detailed content of Checks whether a string can form a palindrome string by swapping character pairs at indices with unequal characters in a binary string. For more information, please follow other related articles on the PHP Chinese website!