Check if a string can be made palindromic by swapping pairs of characters from indices having unequal characters in a Binary String

0 0 14 minutes read

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

// 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 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 not
def 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 not
def canBecomePalindrome(S, B):
 
    if (canBecomePalindromeUtil(S, B)):
        print("Yes")
    else:
        print("No")
 
# Driver code
if __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 not
function 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 not
function canBecomePalindrome(S, B)
{
    if (canBecomePalindromeUtil(S, B))
        document.write("No");
    else
        document.write("Yes");
}
 
// Driver code
var 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 Sonigara
 
def 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 False
 
if __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 zambiatek!