How to split a string into as few palindromes as possible ?

Question

This is an interview question: "You're given a string, and you want to split it into as few strings as possible such that each string is a palindrome". (I guess a one char string is considered a palindrome, i.e. "abc" is split into "a", "b", "c".)

How would you answer it?

Answer 1

O(n^3) solution. Iterate the string recursively. For each letter establish every palindrome with this letter as the start of palindrome. Pay attention to odd and even numbered palindromes. Repeat until end of string. If at the end of string the palindrome count is minimal then remember how you got there. Don't iterate further if sum of current palindromes count and remaining letters in the string is larger than current palindrome count minimum.

An optimization: when discovering palindromes start from the end of the string and search for occurrence of your current letter. Test the substring to "palindromness". Don't start from shortest palindromes, it's not optimal.

Answer 2

You can do this in O(n^2) time using Rabin-Karp fingerprinting to preprocess the string to find all of the palindromes in O(n^2) time. After the preprocessing, you run code similar to the following:

np(string s) {
  int a[s.size() + 1];
  a[s.size()] = 0;
  for (int i = s.size() - 1; i >= 0; i--) {
    a[i] = s.size() - i;
    for (int j = i + 1; j <= s.size(); j++) {
      if (is_palindrome(substr(s, i, j))) // test costs O(1) after preprocessing
        a[i] = min(a[i], 1 + a[j]);
  }
  return a[0];
}

Answer 3

First find all the palindromes in the string such that L[i][j] represents the length of j-th longest palindrome that ends at S[i]. Lets say S is the input string. This could be done in O(N^2) time by first considering length1 palindromes then then length 2 palindromes and so on. Finding Length i palindromes after you know all length i-2 palindromes is the matter of a single character comparison.

This is a dynamic programming problem after that. Let A[i] represent the smallest number of palindrome that Substring(S,0,i-1) can be decomposed into.

A[i+1] = min_{0 <= j < length(L[i])} A[i - L[i][j]] + 1;

Edit based on Micron's request: Here is the idea behind comuting L[i][j]. I just wrote this up to convey the idea, the code may have problems.

// Every single char is palindrome so L[i][0] = 1;
vector<vector<int> > L(S.length(), vector<int>(1,1));

for (i = 0; i < S.length(); i++) {
 for (j = 2; j < S.length; j++) {
   if (i - j + 1 >= 0 && S[i] == S[i-j + 1]) {
     // See if there was a palindrome of length j - 2 ending at S[i-1]
     bool inner_palindrome = false;
     if (j ==2) {
      inner_palindrome = true;
     } else {
       int k = L[i-1].length;
       if (L[i-1][k-1] == j-2 || (k >= 2 && L[i-1][k-2] == j-2)) {
         inner_palindrome = true;
       }
     }
     if (inner_palindrome) {
       L[i].push_back(j);
     }
   } 
 }
}