Given a set of N binary strings of different sizes , we can choose any two binary strings A , B and two valid indexes i , j in those string,we can swap the values present in A[ i ] and B[ j ].Find the maximum number of strings that can be made palindromes using these operations.
Note : We do not need to minimise the operations.
Examples :
Input : N = 2
arr[] = {001,1110111}
Output : 2
Explanation :
We can swap arr[1][3] and arr[2][4] then the resulting strings will be
{000,1111111} and both of them are palindromes
Input : N = 3
arr[] = {0111,1011,11110}
Output : 3
Explanation :
1.
swap arr[1][1] and arr[2][3] then the set would be {1111,1001,11110}
2.
swap arr[1][1] and arr[3][5] then the set would be {0111,1001,11111}
3.
swap arr[1][1] and arr[3][3] then the set would be {1111,1001,11011}
Now all the strings of the given set are plaindrome.
Note : there can be other ways also to convert them to palindromes.
Approach :
Some of the observations that we can make are:
1. The length of the individual strings in the set remains same. 2. If all the strings are of even length and the total number of 1's and 0's among all the strings are even then we can always manipulate the strings to make them palindromes. 3. If any one of the string has odd length then we can make all the strings palindrome irrespective of the total number of 1's and 0's since we can always accomodate the extra 0 or 1 in the odd length string.
Let us take an example to to check the correctness of observation 2 .
Let arr[ ] = {0001, 1111} , now totalZeros = 3 and totalOnes = 5.
Since all the strings in the set are of even length if we put a 1 or 0 in a string we need to put the same character in the second half of the string as well to maintain the palindromic behaviour , but we can not do that because the number of 0’s and 1’s are odd therefore there will always be a single 1 or 0 out of place in one of the string. Therefore only N-1 strings can be made palindrome when all the strings are of even length and total 0’s and 1’s are odd.
Same argument we can use for the obs 3 because in case of atleast one odd length string we can place the extra 0 or 1 in the middle of the odd string thus maintaining the palindromic behaviour which we could not do in previous case.
Implementation :
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum number
// of strings that can be made palindromes
void maximumPossiblePalindromes(vector<string>& values,
int N)
{
// to store the total number of 0s and 1s
int totalZero = 0;
int totalOne = 0;
for (int i = 0; i < N; i++) {
// if any of the string has odd size then ans = N
if (values[i].size() & 1) {
cout << N;
return;
}
for (auto c : values[i]) {
int x = c - '0';
if (x == 1)
totalOne++;
else
totalZero++;
}
}
/// if total 0s are even (1s will be even
/// automaticallys)
if ((totalZero % 2) == 0)
cout << N;
else
cout << N - 1;
return;
}
int main()
{
int N = 5;
// Given array of strings
vector<string> values
= { "0100", "10", "01", "10", "111" };
// function call
maximumPossiblePalindromes(values, N);
return 0;
}