String palindrome c++, Here, suppose there is a string S and a binary string B, both of length N, then the task is to check if the given string S can be made palindromic by repeatedly swapping characters at any pair of indices consisting of unequal characters in the string B.
Examples:
Input: S = “BAA”, B = “100”
Output: Yes
Explanation:
Swapping S[0] and S[1] modifies S to “ABA” and B to “010”.
Input: S = “ACABB”, B = “00000”
Output: No
Below is the implementation of the above approach:
- Step-1: Check if string S can be rearranged to form a palindromic string or not. If found to be false, then print “No”.
- Step-2: Otherwise, if the string S is a palindrome, then print “Yes”.
- Step-3: If the count of 0s and 1s is at least 1, then there always exists a way to swap characters to make the given string S palindromic. Therefore, print “Yes”. Otherwise, print “No”.
C++ program for the above approach:
// C++ program for the above approach #include<bits/stdc++.h> using namespace std; // Utility function to check if string // S can be made palindromic or not bool canBecomePalindromeUtil(string S, string B) { // Stores the number of distinct // characters present in string S unordered_set<char> set; // Traverse the characters of string S for(int i = 0; i < S.size(); i++) { // Insert current character in S set.insert(S[i]); } // Count frequency of each // character of string S map<char, int> map; // Traverse the characters of string S for(int i = 0; i < S.length(); i++) { map[S[i]] += 1; } bool flag = false; // Check for the odd length string if (S.size() % 2 == 1) { // Stores the count of // even and odd frequenct // characters in the string S int count1 = 0, count2 = 0; for(auto e : map) { if (e.second % 2 == 1) { // Update the count of // odd frequent characters count2++; } else { // Update the count of // even frequent characters count1++; } } // If the conditions satisfies if (count1 == set.size() - 1 && count2 == 1) { flag = true; } } // Check for even length string else { // Stores the frequency of // even and odd characters // in the string S int count1 = 0, count2 = 0; for(auto e : map) { if (e.second % 2 == 1) { // Update the count of // odd frequent characters count2++; } else { // Update the count of // even frequent characters count1++; } } // If the condition satisfies if (count1 == set.size() && count2 == 0) { flag = true; } } // If a palindromic string // cannot be formed if (!flag) { return false; } else { // Check if there is // atleast one '1' and '0' int count1 = 0, count0 = 0; for(int i = 0; i < B.size(); i++) { // If current character is '1' if (B[i] == '1') { count1++; } else { count0++; } } // If atleast one '1' and '0' is present if (count1 >= 1 && count0 >= 1) { return true; } else { return false; } } } // Function to determine whether // string S can be converted to // a palindromic string or not void canBecomePalindrome(string S, string B) { if (canBecomePalindromeUtil(S, B)) cout << "Yes"; else cout << "No"; } // Driver code int main() { string S = "ACABB"; string B = "00010"; canBecomePalindrome(S, B); return 0; } // This code is contributed by Kingash
Java Program of above approach:
// Java program for the above approach import java.io.*; import java.util.HashMap; import java.util.HashSet; import java.util.Map; class GFG { // Utility function to check if string // S can be made palindromic or not public static boolean canBecomePalindromeUtil(String S, String B) { // Stores the number of distinct // characters present in string S HashSet<Character> set = new HashSet<>(); // Traverse the characters of string S for (int i = 0; i < S.length(); i++) { // Insert current character in S set.add(S.charAt(i)); } // Count frequency of each // character of string S HashMap<Character, Integer> map = new HashMap<>(); // Traverse the characters of string S for (int i = 0; i < S.length(); i++) { Integer k = map.get(S.charAt(i)); map.put(S.charAt(i), (k == null) ? 1 : k + 1); } boolean flag = false; // Check for the odd length string if (S.length() % 2 == 1) { // Stores the count of // even and odd frequenct // characters in the string S int count1 = 0, count2 = 0; for (Map.Entry<Character, Integer> e : map.entrySet()) { if (e.getValue() % 2 == 1) { // Update the count of // odd frequent characters count2++; } else { // Update the count of // even frequent characters count1++; } } // If the conditions satisfies if (count1 == set.size() - 1 && count2 == 1) { flag = true; } } // Check for even length string else { // Stores the frequency of // even and odd characters // in the string S int count1 = 0, count2 = 0; for (Map.Entry<Character, Integer> e : map.entrySet()) { if (e.getValue() % 2 == 1) { // Update the count of // odd frequent characters count2++; } else { // Update the count of // even frequent characters count1++; } } // If the condition satisfies if (count1 == set.size() && count2 == 0) { flag = true; } } // If a palindromic string // cannot be formed if (!flag) { return false; } else { // Check if there is // atleast one '1' and '0' int count1 = 0, count0 = 0; for (int i = 0; i < B.length(); i++) { // If current character is '1' if (B.charAt(i) == '1') { count1++; } else { count0++; } } // If atleast one '1' and '0' is present if (count1 >= 1 && count0 >= 1) { return true; } else { return false; } } } // Function to determine whether // string S can be converted to // a palindromic string or not public static void canBecomePalindrome(String S, String B) { if (canBecomePalindromeUtil(S, B)) System.out.print("Yes"); else System.out.print("No"); } // Driver Code public static void main(String[] args) String S = "ACABB"; String B = "00010"; canBecomePalindrome(S, B); } }
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(N)
If you want add more values to this website or write content then WhatsApp us.