Splitting a string into the fewest number of palindromes

tags: public draft programming leetcode algorithms computer science

Started 645pm

Question Number 181

Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given a string, split it into as few strings as possible such that each string is a palindrome.

For example, given the input string racecarannakayak, return ["racecar", "anna", "kayak"].

Given the input string abc, return ["a", "b", "c"].

Problem analysis

Call a partition $P$ a list of indices $[i_1, i_2, ... i_K]$ where each index $i_k$ denotes where to split the string. A partition is valid if each substring

$$S[0:i_1], S[i_1:i_2], ... ,S[i_{K}:]$$

is a palindrome.

A partition $P$ is minimal if len(indices) is the smallest for all possible valid partitions.

The recurrence relation is as follows: The minimal partition of $S[0:N]$ is the minimum of minimal partitions of all $S[k:N+1] \forall k <= N$ where $S[0:k]$ is a palindrome.

That is to say, for each k where $S[0:k]$ is a palindrome, recurse into the subproblem of finding a minimal partition for $S[k:N+1]$.

I believe the time complexity is $O(N^2)$. In the worst case each substring is a palindrome, so you have to check all the substrings. With memoisation each lookup of a substring is $O(1)$, and checking whether a substring is a palindrome should also take constant time if a subsubstring already exists (checking if $S[a:b]$ is a palindrome is $O(1)$ if you have memoised $S[a+1, b-1]$). $O(N^2)$ memory complexity.

Pseudocode:

# TODO