Splitting a string into the fewest number of palindromes

Thu Feb 18 2021

tags: 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 PP a list of indices [i1,i2,...iK][i_1, i_2, ... i_K] where each index iki_k denotes where to split the string. A partition is valid if each substring

S[0:i1],S[i1:i2],...,S[iK:]S[0:i_1], S[i_1:i_2], ... ,S[i_{K}:]

is a palindrome.

A partition PP 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]S[0:N] is the minimum of minimal partitions of all S[k:N+1]k<=NS[k:N+1] \forall k <= N where S[0:k]S[0:k] is a palindrome.

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

I believe the time complexity is O(N2)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)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]S[a:b] is a palindrome is O(1)O(1) if you have memoised S[a+1,b1]S[a+1, b-1]). O(N2)O(N^2) memory complexity.