Maximum Palindromes After Operations
Real-world version: Noticeboard Word StripsThe statement here is our own: the same inputs, outputs and technique.
A club noticeboard carries a row of word strips. Strip i currently shows the lowercase letter cards spelling words[i], one card per slot, and no slot is ever left empty.
The steward may pick any two slots anywhere on the board, on the same strip or on two different strips, and trade the cards sitting in them. She may do this as often as she likes, in any order. Every strip keeps the number of slots it started with; only which card sits in which slot ever changes.
A strip reads both ways when the cards along it spell the same sequence read left to right as read right to left.
Return the largest number of strips that can be made to read both ways at the same time.
Examples
Example 1
- Input
- words = ["aabb", "cd", "ef"]
- Output
- 2
The board holds two a cards, two b cards, and one each of c, d, e and f. Moving both a cards onto the two-slot strip and both b cards onto the other two-slot strip leaves them showing `"aa"` and `"bb"`, and the four-slot strip is left holding c, d, e and f, which are four different cards.
Example 2
- Input
- words = ["ab", "ba"]
- Output
- 2
Trading the b on the first strip for the b on the second gives `"aa"` and `"bb"`, and both strips then read the same in either direction.
Example 3
- Input
- words = ["abc", "de"]
- Output
- 0
All five cards on the board are different letters, so any two-slot strip shows two different cards and the three-slot strip shows three.
Example 4
- Input
- words = ["a"]
- Output
- 1
A single slot always reads the same in either direction, so the one strip counts.
Example 5
- Input
- words = ["aab"]
- Output
- 1
Trading the b into the middle slot leaves the strip showing `"aba"`.
Constraints
- 1 <= words.length <= 1000
- 1 <= words[i].length <= 100
- words[i] consists only of lowercase English letters.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def max_palindromes_after_operations(words: list[str]) -> int:public int maxPalindromesAfterOperations(String[] words)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 16 test cases: 16 passed
- Passed: 5 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's