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

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 s开发者_如何学运维tring is considered a palindrome, i.e. "abc" is split into "a", "b", "c".)

How would you answer it?

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);
     }
   } 
 }
} 

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];
}

bool ispalindrome(string inp)
{
    if(inp == "" || inp.length() == 1)
    {
        return true;
    }
    string rev = inp;

    reverse(rev.begin(), rev.end());

    return (rev == inp);
}

int minsplit_count(string inp)
{
    if(ispalindrome(inp))
    {
        return 0;
    }

    int count= inp.length();

    for(int i = 1; i < inp.length(); i++)
    {
        count = min(count, 
                      minsplit_count(inp.substr(0, i))              + 
                      minsplit_count(inp.substr(i, inp.size() - i)) + 
                      1);
    }

    return count;
}

An equivalent problem is that of computing the Snip number of a string.

Suppose you wanted to cut a string using the fewest number of snips, so that each remaining piece was itself a palindrome. The number of such cuts we will call the Snip Number of a string. That is the snip number is always equal to one less than the smallest number of palindromes within a given string. Every string of length n has snip number at most n-1, and each palindrome has snip number 0. Here is working python code.

def snip_number(str):
    n=len(str)
 
 #initialize Opt Table
 # Opt[i,j] = min number of snips in the substring str[i...j]
 
    Opt=[[0 for i in range(n)] for j in range(n) ]
 
 #Opt of single char is 0
    for i in range(n):
     Opt[i][i] = 0
 
 #Opt for adjacent chars is 1 if different, 0 otherwise
    for i in range(n-1):
     Opt[i][i+1]= 1 if str[i]!=str[i+1] else 0
 
 
# we now define sil as (s)substring (i)interval (l) length of the
# interval [i,j] --- sil=(j-i +1) and j = i+sil-1
 
# we compute Opt table entry for each sil length and
# starting index i
 
    for sil in range(3, n+1):
     for i in range(n-sil+1):
       j = i+sil-1
       if (str[i] == str[j] and Opt[i+1][j-1]==0):
         Opt[i][j] = 0
       else:
         snip= min( [(Opt[i][t]+ Opt[t+1][j] + 1 ) for t in range(i,j-1)])
         Opt[i][j] = snip

    return Opt[0][len(str)-1]
#end function snip_number()
mystr=[""for i in range(4)]         
mystr[0]="abc"
mystr[1]="ohiho"
mystr[2]="cabacdbabdc"
mystr[3]="amanaplanacanalpanama aibohphobia "


for i in range(4):
     print mystr[i], "has snip number:", snip_number(mystr[i])
     
# abc has snip number: 2
# ohiho has snip number: 0
# cabacdbabdc has snip number: 2
# amanaplanacanalpanama aibohphobia  has snip number: 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.