# Splitting a string into the fewest number of palindromes

Thu Feb 18 2021tags: 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
```