Given a string S and a binary string B, both of length N, 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
Approach: Follow the below steps to solve this problem:
- Check if string S can be rearranged to form a palindromic string or not. If found to be false, then print “No”.
- Otherwise, if the string S is a palindrome, then print “Yes”.
- 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”.
Below is the implementation of the above approach:
C++
// 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 notbool 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 frequent // 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 notvoid canBecomePalindrome(string S, string B){ if (canBecomePalindromeUtil(S, B)) cout << "Yes"; else cout << "No";}// Driver codeint main(){ string S = "ACABB"; string B = "00010"; canBecomePalindrome(S, B); return 0;}// This code is contributed by Kingash |
Java
// Java program for the above approachimport 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 frequency // 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); }} |
Python3
# Python3 program for the above approach # Utility function to check if string# S can be made palindromic or notdef canBecomePalindromeUtil(S, B): # Stores the number of distinct # characters present in string S s = set(S) # Count frequency of each # character of string S map = {} # Traverse the characters of string S for i in range(len(S)): if S[i] in map: map[S[i]] += 1 else: map[S[i]] = 1 flag = False # Check for the odd length string if (len(S) % 2 == 1): # Stores the count of # even and odd frequency # characters in the string S count1 = 0 count2 = 0 for e in map: if (map[e] % 2 == 1): # Update the count of # odd frequent characters count2 += 1 else: # Update the count of # even frequent characters count1 += 1 # If the conditions satisfies if (count1 == len(s) - 1 and count2 == 1): flag = True # Check for even length string else: # Stores the frequency of # even and odd characters # in the string S count1 = 0 count2 = 0 for e in map: if (map[e] % 2 == 1): # Update the count of # odd frequent characters count2 += 1 else: # Update the count of # even frequent characters count1 += 1 # If the condition satisfies if (count1 == len(s) and count2 == 0): flag = True # If a palindromic string # cannot be formed if (not flag): return False else: # Check if there is # atleast one '1' and '0' count1 = 0 count0 = 0 for i in range(len(B)): # If current character is '1' if (B[i] == '1'): count1 += 1 else: count0 += 1 # If atleast one '1' and '0' is present if (count1 >= 1 and count0 >= 1): return True else: return False # Function to determine whether# string S can be converted to# a palindromic string or notdef canBecomePalindrome(S, B): if (canBecomePalindromeUtil(S, B)): print("Yes") else: print("No")# Driver codeif __name__ == "__main__": S = "ACABB" B = "00010" canBecomePalindrome(S, B)# This code is contributed by AnkThon |
C#
using System;using System.Collections.Generic;class MainClass { // Utility function to check if string // S can be made palindromic or not public static bool CanBecomePalindromeUtil(string S, string B) { // Stores the number of distinct // characters present in string S HashSet<char> set = new HashSet<char>(); // Traverse the characters of string S for (int i = 0; i < S.Length; i++) { // Insert current character in S set.Add(S[i]); } // Count frequency of each // character of string S Dictionary<char, int> map = new Dictionary<char, int>(); // Traverse the characters of string S for (int i = 0; i < S.Length; i++) { int k = 0; if (map.ContainsKey(S[i])) { k = map[S[i]]; } map[S[i]] = k + 1; } bool flag = false; // Check for the odd length string if (S.Length % 2 == 1) { // Stores the count of // even and odd frequency // characters in the string S int count1 = 0, count2 = 0; foreach(var e in map) { if (e.Value % 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.Count - 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; foreach(var e in map) { if (e.Value % 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.Count && 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[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 static void CanBecomePalindrome(string S, string B) { if (CanBecomePalindromeUtil(S, B)) Console.WriteLine("Yes"); else Console.WriteLine("Np"); } // Driver code public static void Main(string[] args) { string S = "ACABB"; string B = "00010"; CanBecomePalindrome(S, B); }}// This code is contributed by phasing17. |
Javascript
<script>// Javascript program for the above approach // Utility function to check if string// S can be made palindromic or notfunction canBecomePalindromeUtil(S, B){ // Stores the number of distinct // characters present in string S var st = new Set() var i; // Traverse the characters of string S for(i = 0; i < S.length; i++) { // Insert current character in S st.add(S[i]); } // Count frequency of each // character of string S var mp = new Map(); // Traverse the characters of string S for(i = 0; i < S.length; i++) { if (mp.has(S[i])) mp.set(S[i], mp.get(S[i])) else mp.set(S[i], 1); } var flag = false; // Check for the odd length string if (S.length % 2 == 1) { // Stores the count of // even and odd frequency // characters in the string S var count1 = 0, count2 = 0; for(const [key, value] of Object.entries(mp)) { if (value % 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 == st.size - 1 && count2 == 1) { flag = true; } } // Check for even length string else { // Stores the frequency of // even and odd characters // in the string S var count1 = 0, count2 = 0; for (const [key, value] of Object.entries(mp)) { if (value % 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 == st.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' var count1 = 0, count0 = 0; for(i = 0; i < B.length; 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 notfunction canBecomePalindrome(S, B){ if (canBecomePalindromeUtil(S, B)) document.write("No"); else document.write("Yes");}// Driver codevar S = "ACABB";var B = "00010";canBecomePalindrome(S, B); // This code is contributed by SURENDRA_GANGWAR</script> |
Output
Yes
Time Complexity: O(N log N)
Auxiliary Space: O(1) because set and map are storing characters and frequency of characters so it will be using constant space
Approach 2: Frequency Array:
Here’s another approach to solve the problem:
- Count the frequency of each character in string S using an array of size 26 (assuming only lowercase alphabets are present in S). Let’s call this array freq.
- Traverse string B and count the number of 1’s and 0’s. Let’s call them count1 and count0 respectively.
- Traverse the freq array and count the number of odd frequency characters. Let’s call this count_odd.
- If S is of odd length, then there should be only one odd frequency character, and all other characters should have even frequency. If S is of even length, then all characters should have even frequency.
- If count_odd is greater than 1, then it is not possible to form a palindrome from S.
- If count1 and count0 are both greater than zero, then it is possible to form a palindrome from S.
Here’s the C++ code for this approach:
C++
#include<bits/stdc++.h>using namespace std;bool canFormPalindrome(string S, string B) { int freq[26] = {0}; int count1 = 0, count0 = 0, count_odd = 0; for(char c : S) { freq++; } for(char c : B) { if(c == '1') count1++; if(c == '0') count0++; } for(int i = 0; i < 26; i++) { if(freq[i] % 2 == 1) count_odd++; } if(S.length() % 2 == 0 && count_odd > 0) return false; if(S.length() % 2 == 1 && count_odd > 1) return false; if(count1 > 0 && count0 > 0) return true; return false;}int main() { string S = "ACABB"; string B = "00010"; if(canFormPalindrome(S, B)) cout << "Yes"; else cout << "No"; return 0;} |
Java
public class Main { static boolean canFormPalindrome(String S, String B) { int[] freq = new int[26]; int count1 = 0, count0 = 0, count_odd = 0; for (char c : S.toCharArray()) { if (c >= 'a' && c <= 'z') { // check if c is a lowercase English letter freq++; } } for (char c : B.toCharArray()) { if (c == '1') count1++; if (c == '0') count0++; } for (int f : freq) { if (f % 2 == 1) count_odd++; } if (S.length() % 2 == 0 && count_odd > 0) return false; if (S.length() % 2 == 1 && count_odd > 1) return false; if (count1 > 0 && count0 > 0) return true; return false; } public static void main(String[] args) { String S = "ACABB"; String B = "00010"; if (canFormPalindrome(S, B)) System.out.println("Yes"); else System.out.println("No"); }}// This code is contributed by rudra1807raj |
Python3
# Added by ~Nikunj Sonigaradef canFormPalindrome(S, B): freq = [0] * 26 count1 = 0 count0 = 0 count_odd = 0 for c in S: if 'a' <= c <= 'z': freq[ord(c) - ord('a')] += 1 for c in B: if c == '1': count1 += 1 if c == '0': count0 += 1 for i in range(26): if freq[i] % 2 == 1: count_odd += 1 if len(S) % 2 == 0 and count_odd > 0: return False if len(S) % 2 == 1 and count_odd > 1: return False if count1 > 0 and count0 > 0: return True return Falseif __name__ == "__main__": S = "ACABB" B = "00010" if canFormPalindrome(S, B): print("Yes") else: print("No") |
C#
using System;class Program{ // Function to check if it's possible to form a palindrome of the given string 'S' using binary string 'B' static bool CanFormPalindrome(string S, string B) { int[] freq = new int[26]; // Create an array to store character frequency for 'S' int count1 = 0, count0 = 0, countOdd = 0; // Initialize counters for '1's, '0's, and odd character frequencies // Convert 'S' to lowercase to make the comparison case-insensitive S = S.ToLower(); // Calculate character frequencies for 'S' foreach (char c in S) { freq++; // Increment the frequency count for each character } // Count the number of '1's and '0's in the binary string 'B' foreach (char c in B) { if (c == '1') count1++; // Count '1's if (c == '0') count0++; // Count '0's } // Count the number of characters in 'S' with odd frequencies foreach (int f in freq) { if (f % 2 == 1) countOdd++; // Increment 'countOdd' if a character has an odd frequency } // Check the conditions for forming a palindrome if (S.Length % 2 == 0 && countOdd > 0) return false; // If 'S' has an even length and there's an odd-frequency character, it's not possible to form a palindrome if (S.Length % 2 == 1 && countOdd > 1) return false; // If 'S' has an odd length and there are more than one odd-frequency characters, it's not possible to form a palindrome if (count1 > 0 && count0 > 0) return true; // If both '1's and '0's are present in 'B', it's possible to form a palindrome return false; // If none of the above conditions are met, it's not possible to form a palindrome } static void Main() { string S = "ACABB"; string B = "00010"; // Check if it's possible to form a palindrome and print the result if (CanFormPalindrome(S, B)) Console.WriteLine("Yes"); else Console.WriteLine("No"); }} |
Javascript
function canFormPalindrome(S, B) { let freq = new Array(26).fill(0); let count1 = 0, count0 = 0, count_odd = 0; for(let c of S) { freq++; } for(let c of B) { if(c === '1') count1++; if(c === '0') count0++; } for(let i = 0; i < 26; i++) { if(freq[i] % 2 === 1) count_odd++; } if(S.length % 2 === 0 && count_odd > 0) return false; if(S.length % 2 === 1 && count_odd > 1) return false; if(count1 > 0 && count0 > 0) return true; return false;}let S = "ACABB";let B = "00010";if(canFormPalindrome(S, B)) console.log("Yes");else console.log("No"); |
Output:
Yes
Time Complexity: O(n) where n is the length of the input string S
Auxiliary Space :O(k), where k is the number of distinct characters in the input string S.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
