# Splitting a string into the fewest number of palindromes

Thu Feb 18 2021

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