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++

Share Your Love

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.

Share Your Love
Avatar photo
Lingaraj Senapati

Hey There! I am Lingaraj Senapati, the Founder of lingarajtechhub.com My skills are Freelance, Web Developer & Designer, Corporate Trainer, Digital Marketer & Youtuber.

Articles: 429

Newsletter Updates

Enter your email address below to subscribe to our newsletter