Longest Palindromic Subsequence
Real-world version: Longest Mirrored Card RunThe statement here is our own: the same inputs, outputs and technique.
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 starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def mirrored_run(cards: str) -> int:public int mirroredRun(String cards)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 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