Minimum Insertion Steps to Make a String Palindrome
Real-world version: Fewest Tiles to Mirror the StripThe statement here is our own: the same inputs, outputs and technique.
A mosaic strip is written as strip, one lowercase letter per tile, read left to right. Each letter names a tile colour.
In one step you may buy a tile of any colour and slide it into the strip at any position: in front of the first tile, between two neighbouring tiles, or after the last tile. Tiles already on the strip are never removed and never change their order.
A strip is mirrored when the colours read from left to right are the same as the colours read from right to left.
Return the fewest steps needed to leave the strip mirrored.
Examples
Example 1
- Input
- strip = "cobalt"
- Output
- 5
Buying five tiles gives `tlabocobalt`, which reads the same in both directions and keeps the six original tiles in their original order.
Example 2
- Input
- strip = "aaab"
- Output
- 1
One bought tile is enough: sliding a `b` in front gives `baaab`, which reads the same both ways.
Example 3
- Input
- strip = "ggrgg"
- Output
- 0
This strip already reads the same in both directions, so no tile is bought.
Constraints
- 1 <= strip.length <= 500
- strip consists 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 fewest_inserts(strip: str) -> int:public int fewestInserts(String strip)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 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