How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at IBM.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at IBM during technical interviews.

Maximize palindromic strings after character swaps

Company: IBM

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given an integer n and an array of n lowercase strings `arr`. Operation (can be performed any number of times): choose two different strings `arr[i]` and `arr[j]`, pick one character from each string, and swap those two characters. After performing any sequence of such swaps, return the **maximum possible number of strings in `arr` that are palindromes**. Notes: - You may swap characters between any pair of strings, and you may repeat operations indefinitely. - Each string’s **length must remain the same**. Example: - Input: `arr = ["pass", "sas", "asps", "df"]` - Output: `3` (it is possible to make 3 of the strings palindromes).

Quick Answer: This question evaluates proficiency in string manipulation, combinatorial character-count reasoning, and redistribution of characters under constrained swap operations within the Coding & Algorithms domain.

You are given an array `arr` of `n` lowercase strings. **Operation (repeatable any number of times):** choose two *different* strings `arr[i]` and `arr[j]`, pick one character from each, and swap those two characters. Because any character can be swapped with any other through a sequence of single swaps, the characters become a single global pool that you may redistribute freely among the strings. The only hard constraint is that **each string keeps its original length**. Return the **maximum number of strings in `arr` that can simultaneously be palindromes** after performing any sequence of swaps. **Example** - Input: `arr = ["pass", "sas", "asps", "df"]` - Output: `3` Three of the four strings can be made palindromes simultaneously. **Key idea.** A string of length `L` is a palindrome iff its symmetric positions are equal, so it needs `L // 2` matching *pairs* of characters, plus (for odd `L`) one extra character for the middle slot. Across the whole array you have a fixed budget of pairs (`sum(count // 2)` over all characters) and of leftover single characters. A pair may also be split to supply a middle character. Greedily satisfy the shortest strings first to maximize how many you can complete.

Constraints

1 <= n <= 10^5
1 <= len(arr[i])
Sum of all string lengths fits in memory (e.g. <= 10^6)
All characters are lowercase English letters ('a'-'z')
Each string's length must remain unchanged after any swaps

Examples

Input: (["pass", "sas", "asps", "df"],)

Expected Output: 3

Explanation: Letters available: a x3, s x4, p x2, d x1, f x1 -> pairs = 1+2+1 = 4, singles = 1(a)+1(d)+1(f) = 3. Shortest first: "df"(len2) needs 1 pair -> pairs 3; "sas"(len3) needs 1 pair + 1 middle -> pairs 2, use a single; "pass"/"asps"(len4) needs 2 pairs -> 1 of them completes (pairs 0). 3 strings become palindromes.

Input: (["abc"],)

Expected Output: 0

Explanation: Only one string and no other to swap with. a,b,c are all distinct: 0 pairs, 3 singles. A length-3 palindrome needs 1 pair, which doesn't exist, so it cannot be made a palindrome.

Input: (["ab", "cd"],)

Expected Output: 0

Explanation: Letters a,b,c,d each appear once: 0 pairs total. Each even-length string needs 1 pair, so neither can be completed.

Input: (["aa", "bb", "cc"],)

Expected Output: 3

Explanation: Each string is already a palindrome; pairs = 3, every length-2 string needs exactly 1 pair, so all 3 succeed.

Input: (["ab", "ba"],)

Expected Output: 2

Explanation: Letters a x2, b x2 -> pairs = 2. Redistribute to "aa" and "bb" (both length 2, length preserved); both become palindromes.

Input: ([],)

Expected Output: 0

Explanation: Empty array: no strings, so the answer is 0.

Input: (["abcd", "abcd"],)

Expected Output: 2

Explanation: Letters a,b,c,d each appear twice -> pairs = 4. Each length-4 string needs 2 pairs, and 4 pairs cover both, so both can be made palindromes (e.g. "abba").

Input: (["xyz", "xy", "x"],)

Expected Output: 3

Explanation: Letters x x3, y x2, z x1 -> pairs = 1(x)+1(y) = 2, singles = 1(x)+1(z) = 2. Shortest first: "x"(len1) uses a single; "xy"(len2) uses 1 pair; "xyz"(len3) uses the last pair + a single middle. All 3 succeed.

Input: (["aaaa"],)

Expected Output: 1

Explanation: "aaaa" is already a palindrome; pairs = 2 cover its 2 required pairs.

Input: (["abc", "abc", "abc"],)

Expected Output: 3

Explanation: Letters a x3, b x3, c x3 -> pairs = 3, singles = 3. Each length-3 string needs 1 pair + 1 middle single; 3 pairs and 3 singles exactly satisfy all three strings (e.g. "aba", "cac", ...).

Hints

Single swaps between arbitrary string pairs can be chained to achieve any permutation of all characters, so treat every character as part of one shared global pool. Only each string's length is fixed.
A string of length L is a palindrome iff you can fill its L//2 symmetric position-pairs with equal characters (each costs one 'pair'), and for odd L place any single character in the middle slot.
Compute the global budget: pairs = sum(count // 2) over all characters, and singles = sum(count % 2). A leftover pair can always be split into two singles if you need a middle character.
To maximize the count, finish the strings that require the fewest pairs first — sort by length ascending and greedily spend pairs (and a middle char for odd lengths) until you run out.

Quick Overview

This question evaluates proficiency in string manipulation, combinatorial character-count reasoning, and redistribution of characters under constrained swap operations within the Coding & Algorithms domain.