0257MediumStringDynamic Programming

Longest Mirrored Card Run

Tracked in this browser only

Trains the technique from

LeetCode 516Longest Palindromic Subsequence

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 curator has a rail of exhibit cards. The string cards gives one lowercase letter per card, in the order the cards sit on the rail; the letter is the card's category.

The curator may lift any cards off the rail, including none of them, but may not shuffle the ones left behind, which keep their original order. Call what is left a run, and call a run mirrored when reading it left to right gives the same letters as reading it right to left.

Return the number of cards in the longest mirrored run the curator can leave on the rail. A run of one card is mirrored, so the answer is at least 1.

Examples

Example 1

Input: cards = "abxcba"
Output: 5

Lifting the c leaves a, b, x, b, a on the rail, which reads the same from either end, so 5 cards stay.

Example 2

Input: cards = "abab"
Output: 3

Lifting the last b leaves a, b, a on the rail, which reads the same from either end, so 3 cards stay.

Example 3

Input: cards = "aabbaa"
Output: 6

The rail already reads the same in both directions, so the curator lifts nothing and all 6 cards stay.

Constraints

1 <= cards.length <= 1000
cards consists of lowercase English letters only

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 mirrored_run(cards: str) -> int:

Java

public int mirroredRun(String cards)

The intended approach

Time O(n^2) for n cards: one entry per pair of ends, each settled in O(1).Space O(n) for the two live rows.

Fill in the answer for every stretch of the rail, working from the short stretches outwards. When the two end cards of a stretch carry the same letter, both are kept and the stretch is worth two more than the stretch inside them; when they differ, one end or the other has to go, so the stretch is worth the better of the two stretches that drop one end. Only two rows are ever live at once, the row being filled and the row for stretches opening one card further right, so the table collapses to those two.

Pythonentry point: mirrored_run

def mirrored_run(cards):
    span = len(cards)
    if span == 0:
        return 0
    # rightward[j] is the answer for the stretch that opens one card further
    # right than the stretch being filled in
    rightward = [0] * span
    current = rightward
    for left in range(span - 1, -1, -1):
        current = [0] * span
        current[left] = 1
        for right in range(left + 1, span):
            if cards[left] == cards[right]:
                current[right] = rightward[right - 1] + 2
            else:
                keep_left = rightward[right]
                keep_right = current[right - 1]
                current[right] = keep_left if keep_left >= keep_right else keep_right
        rightward = current
    return current[span - 1]

The obvious version

Enumerate every subset of the cards, keep the ones that read the same reversed, and report the largest size. O(2^n * n).

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_mirrored_run(cards):
    span = len(cards)
    best = 0
    for mask in range(1, 1 << span):
        picked = [cards[i] for i in range(span) if mask >> i & 1]
        if picked == picked[::-1] and len(picked) > best:
            best = len(picked)
    return best

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
3 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