Maximum number of binary strings that can be made palindromes

Updated

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;
}
Comment
Next tutorial
Mithlesh Upadhyay Published 18 Nov 2026 · 3 min read

Mithlesh Upadhyay is a Computer Science and AI expert from Madhya Pradesh with strong academic background (BE in CSE and M.Tech in AI) and over six years of experience in technical content development. He has contributed tech articles, led teams, and worked in Full Stack Development and Data Science. He founded the w3colleges.org portal for learning resources.

Related tutorials