# Check if a string can be made palindromic by swapping pairs of characters from indices having unequal characters in a Binary String. | string palindrome c++

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
}

// 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.