1209. How Many Ways to Cut a String Into Palindromes

A string of lowercase letters is to be cut into consecutive pieces, each reading the same forwards and backwards. Report how many such cuts there are.

Problem #1208 prints them for strings up to 14 characters. This counts them up to 24, and the limit moved because the method changed.

aab -> 2 aaaa -> 8 twenty-four letter a -> 8388608 twenty-four distinct -> 1

## What most people try first

Take the enumeration from #1208 and count the leaves instead of printing them. That is correct and it is hopeless at 24 equal characters, where the answer is 2^23 = 8388608: the work is proportional to the answer, and a program whose cost is its answer cannot do better than its answer.

## The canonical state

Ask what a node of that enumeration needs in order to know how many ways there are to finish. At the node where the string before position i has been cut up, the remaining choices are the palindromic pieces starting at i, and then the choices after those. Nothing in that depends on how the part before i was cut. The number of completions is a function of i alone.

f(i) = 1 when i == n f(i) = sum over j > i with pal[i][j] of f(j)

So i is a canonical state: there are n + 1 of them, each computed once, and each costs O(n). The exponential walk becomes O(n^2) arithmetic, which is the same recursion with the same correctness argument in a different complexity class.

## 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.

## Why it is correct

The cuts of s starting at i are in one-to-one correspondence with the pairs consisting of a first palindromic piece s[i .. j-1] and a cut of the rest starting at j. Different first pieces give different cuts, because the first piece has a different length, and for a fixed first piece the cuts of the rest are counted by f(j). So the sum counts each cut exactly once. The empty remainder has exactly one cut, the empty one, which is why f(n) is 1 and not 0; getting that base case wrong gives an answer of 0 for every input, which is the single most common way to break this.

## Overflow

The largest value the constraints allow is 2^23 = 8388608, reached by 24 equal characters, since every one of the 2^(n-1) cuts of such a string is palindromic. That is far below INT_MAX = 2147483647, so a 32-bit counter is correct and nothing needs a wide type. Pushing the limit to 33 equal characters would reach 2^32 and genuinely overflow, which is why the limit is 24.

## Cost

O(n^2) time and O(n) memory for the memo, against O(2^(n-1)) for the enumeration. At n = 24 that is 24 table entries instead of eight million leaves.

Constraints - `1 ≤ length of the string ≤ 24` - every character is a lowercase letter - the answer is at most `2^23 = 8388608`, so it fits in a signed 32-bit integer