Splitting a string into the fewest number of palindromesThu Feb 18 2021
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
["racecar", "anna", "kayak"].
Given the input string
["a", "b", "c"].
partition a list of indices
where each index denotes where to split the string.
A partition is valid if each substring
is a palindrome.
A partition is minimal if
the smallest for all possible valid partitions.
The recurrence relation is as follows: The minimal partition of is the minimum of minimal partitions of all where is a palindrome.
That is to say, for each k where is a palindrome, recurse into the subproblem of finding a minimal partition for .
I believe the time complexity is . 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 , and checking whether a substring is a palindrome should also take constant time if a subsubstring already exists (checking if is a palindrome is if you have memoised ). memory complexity.