0417MediumArrayHash TableStringGreedySortingCounting

Noticeboard Word Strips

Tracked in this browser only

Trains the technique from

LeetCode 3035Maximum Palindromes After Operations

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_palindromes_after_operations(words: list[str]) -> int:

Java

public int maxPalindromesAfterOperations(String[] words)

The intended approach

Time O(T + n log n) for n strips holding T cards in total: one pass to tally the cards, one sort of the n lengths, one pass over the sorted lengths.Space O(n) for the sorted list of lengths, plus a fixed 26-slot tally.

Because a trade may join any two slots on the board, a strip's own starting letters carry no weight; what matters is the board's whole stock of cards and the strip lengths. Tally the 26 letters across every strip and add up half of each tally to get how many matched pairs the board can seat. A strip of length L is satisfied by L // 2 seated pairs, with an odd length taking one spare card in the middle slot, and spare cards are always left when the pairs suffice. Sort the lengths, then spend pairs on strips from the shortest upward, stopping at the first strip the remaining pairs cannot cover.

Pythonentry point: max_palindromes_after_operations

def max_palindromes_after_operations(words):
    # Swapping is unrestricted, so only two things survive: how many matched
    # letter pairs the whole board can supply, and each strip's length. A strip
    # of length L reads the same both ways once L // 2 pairs are seated on it,
    # and any single letters left over cover the odd middles.
    tally = [0] * 26
    for strip in words:
        for card in strip:
            tally[ord(card) - 97] += 1
    pairs = 0
    for count in tally:
        pairs += count // 2
    lengths = sorted(len(strip) for strip in words)
    done = 0
    for length in lengths:
        need = length // 2
        if need > pairs:
            break
        pairs -= need
        done += 1
    return done

The obvious version

Count the board's matched pairs, then try every subset of strips: a subset is reachable when the pairs its lengths ask for do not exceed the supply. Report the size of the largest reachable subset. Exponential in the number of strips.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_palindromes_after_operations(words):
    tally = {}
    for strip in words:
        for card in strip:
            tally[card] = tally.get(card, 0) + 1
    supply = 0
    for card in tally:
        supply += tally[card] // 2
    n = len(words)
    best = 0
    for mask in range(1 << n):
        chosen = 0
        need = 0
        bit = 0
        while bit < n:
            if mask >> bit & 1:
                chosen += 1
                need += len(words[bit]) // 2
            bit += 1
        if need <= supply and chosen > best:
            best = chosen
    return best

How this problem was checked

Reference solution executed against 16 test cases — 16 passed
5 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in