Show problems as
Classic problem #131MediumStringDynamic ProgrammingBacktracking

Palindrome Partitioning

Real-world version: Bead Strand Cuts
Tracked in this browser only
Read Palindrome Partitioning on LeetCode(opens in a new tab)

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

A jeweller has one long strand of beads. strand is a string of lowercase letters giving the bead colour codes from the clasp outwards, one letter per bead.

She wants to snip the strand into consecutive pieces so that every piece is symmetric: reading a piece from either end must give the same sequence of codes. A piece of one bead counts as symmetric, and every bead must end up in exactly one piece.

Return every way of snipping the strand. Each way is the list of its pieces from the clasp outwards; the ways themselves may come back in any order.

Examples

Example 1

Input
strand = "abb"
Output
[["a", "b", "b"], ["a", "bb"]]

Cutting after every bead always works. The only other option is keeping the two b beads together, since "ab" and "abb" are not symmetric.

Example 2

Input
strand = "cbbc"
Output
[["c", "b", "b", "c"], ["c", "bb", "c"], ["cbbc"]]

Single beads always work, the middle pair can be kept whole, and the entire strand already reads the same from either end.

Example 3

Input
strand = "z"
Output
[["z"]]

A single bead admits no cut at all, so there is exactly one way and it is the whole strand.

Constraints

  • 1 <= strand.length <= 16
  • strand contains lowercase English letters only

The values you return may be in any order.

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 strand_cuts(strand: str) -> list[list[str]]:
Java
public List<List<String>> strandCuts(String strand)

More on the same topics