Show problems as
Classic problem #132HardStringDynamic Programming

Palindrome Partitioning II

Real-world version: Mirror-Reading Ribbon Snips
Tracked in this browser only
Read Palindrome Partitioning II on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A dyeing line prints a long strip of colour marks. The strip reaches the finishing bench as ribbon, a string of lowercase letters naming the dye at each point along the strip from its left end.

Call a length of ribbon mirror-reading when its marks spell the same sequence scanned from either end. The finisher may snip straight across the strip at any point between two neighbouring marks, and every piece that remains afterwards must be mirror-reading. Return the fewest snips that leaves the strip in that state. A piece holding a single mark is mirror-reading, so some number of snips always works.

Examples

Example 1

Input
ribbon = "civicap"
Output
2

Snipping after the fifth mark and again after the sixth leaves the pieces `civic`, `a` and `p`. Each of the three spells the same sequence from either end.

Example 2

Input
ribbon = "aabba"
Output
1

A single snip after the first mark leaves `a` and `abba`, and both pieces read the same from either end.

Example 3

Input
ribbon = "zzzz"
Output
0

The strip as delivered already spells the same sequence from either end, so the finisher hands it on untouched.

Constraints

  • 1 <= ribbon.length <= 2000
  • ribbon holds 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.

Python
def fewest_ribbon_snips(ribbon: str) -> int:
Java
public int fewestRibbonSnips(String ribbon)

More on the same topics