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.

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.

Hints

  1. 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.
  2. 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.
  3. 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.
  4. 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.

Loading coding console...