1208. Every Way to Cut a String Into Palindromes

A string of lowercase letters is to be cut into consecutive pieces, with every piece reading the same forwards and backwards. Print every such cut.

Single characters are palindromes, so cutting between every pair of letters always works and there is always at least one answer.

aab a a b aa b

## What most people try first

Choose which of the n - 1 gaps to cut at, over all 2^(n-1) subsets, then test each of the resulting pieces. That is correct and it tests the constraint only after the whole cut is decided, so a cut whose first piece is already not a palindrome is still built in full and all of its completions are generated. At n = 14 that is 8192 subsets, each costing O(n^2) to check, when the real answer may be a single line.

Deciding the pieces left to right instead lets the constraint be tested as each piece is chosen, and a piece that fails costs one rejected candidate rather than a subtree.

## The order the splits are printed in

A set of splits has no order anyone can guess, so the order is part of the specification. Print the splits in increasing order of their sequence of PIECE LENGTHS, compared position by position: the split whose first piece is shorter comes first, and when the first pieces are the same length the second pieces decide, and so on.

That rule is a total order, because two different splits of the same string always differ in their length sequences. There is no need to sort for it either: a recursion that chooses the NEXT piece shortest first, and recurses fully inside each choice before trying a longer one, emits the splits in exactly that order. Choosing the pieces in increasing length at every step is the whole mechanism.

## Testing a piece for being a palindrome

Checking one candidate piece by walking it from both ends costs O(n), and the search asks the question once per start and end pair, so the same questions get asked many times. Work out the answers once instead:

for every start i and end j: pal[i][j] = true when s[i .. j-1] reads the same backwards

That is O(n^3) to build by the direct method and O(n^2) entries, after which every test inside the search is one array lookup. For the sizes here the build cost does not matter; what matters is that the test inside the recursion is constant time, because that is the loop that runs exponentially often.

## The method

go(i): # the string before i is already cut up if i == n: print the pieces; return for j in i+1 .. n: if pal[i][j]: push s[i .. j-1]; go(j); pop

The push and the matching pop are the choose and undo. The pop is easy to forget and the symptom is distinctive: every printed line is longer than it should be, because the pieces of earlier answers are still in the list.

## Why it is correct

Every cut the recursion reaches has palindromic pieces, since a piece is only pushed when the table says it is one. Every palindromic cut is reached, because at each position the loop tries every possible next piece and rejects none that the constraint permits. And each is reached once, because the cuts are determined by the sequence of piece lengths, which the recursion chooses one value at a time.

## The settled boundaries

A one-character string has one answer, itself. A string of n distinct characters has exactly one answer, all single characters, since no two-character or longer substring can be a palindrome. A string of n equal characters has 2^(n-1) answers, every cut at once, which is the largest the output can be and is why the length limit is 14.

## Cost

One node per palindromic prefix cut, plus O(n) to print each answer. The O(n^2) table build is paid once and is dominated by the output on every input where the output is large.

Constraints - `1 ≤ length of the string ≤ 14` - every character is a lowercase letter