CareerCup

I think DP could be doable here. Let T[i,j] stores minimum number of palindromic substring that form substring S[i...j].

Initially, T[i,i] = 1. To compute T[i,j] for i+1 <= j <= n, first check if S[i...j] is palindrome. If it's, T[i,j] = 1. Else, T[i,j] = Min (T[i,k] + T[k+1,j]) for i <= k < j. This leads O(n^3) solution. There probably exists some O(n^2) solution, I guess.

It can be solved by simple DP

static int minCutsforPalindrome(String str){
if(str == null)
return -1;
if(str.length()<2)
return str.length();

int[] min = new int[str.length()+1];
min[0] = 0;
min[1] = 1;
for(int i =2;i<=str.length();i++){
min[i] = min[i-1] + 1;
int p = hasPalindrome(str,i-1);
if(p!=-1){
min[i] = Math.min(min[i], 1+min[p]);
}
}
return min[str.length()]-1;
}

private static int hasPalindrome(String str, int index) {
for(int i=0;i<index;i++){
if(isPalindrome(str.substring(i,index+1)))
return i;
}
return -1;
}

private static boolean isPalindrome(String str) {
if(str.length()<=1)
return true;
int i =0;
int j = str.length() - 1;
while(i<j){
if(str.charAt(i) == str.charAt(j)){
i++;
j--;
}else{
return false;
}
}
return true;
}

if for given string of size n you check if string(1...N-1) is palindrome, and check if 0..n-1 and 1...n cases. returning maximum substring length in any case.
As I see each char is checked 3 times max, so running time is O(n). Where's my mistake?

do a recursion like this: (can be easily modified to remember maximum in any case and select best division in O(n).

int getMinimimNumberOfSubstring(string s) {
 if (s.length == 1) { return 1; };
 max_mid_sub = getMinimimNumberOfSubstring(s.substring(1, s.length-1)); //get middle
 
 int maxSub = 1;
 if (max_mid_sub.length == s.length -2) { //its maximum
    //middle is a max, check if our 0 and n-1 creating palindrome
    if (s.substring(0,1).equals(s.substring(s.length-2,s.length-1))) {
        return max_min_sub.length + 2; 
    else {
        maxSub = max(max_min_sub.length, 1); //string and borders
 }

 //check 0...n-2 and 1...n-1 cases
 return max(maxSub,
            getMinimimNumberOfSubstring(s.substring(1)),
            getMinimimNumberOfSubstring(s.substring(0, s.length-1));
}

<pre lang="" line="1" title="CodeMonkey79135" class="run-this">//To break a long string to minimum substring which are palindromes

package com.stringtopalindome;

import java.util.*;

public class StringToPalindrome {

private static List<String> out = new ArrayList<String>();

public static void main(String[] args)
{
String input ="mnopabcdcbanhohnp";

generatePalindrome(input);

for(String output:out)
{
System.out.println(output);
}

}

//To generate palindrome inside input to out
private static void generatePalindrome(String input) {

char[] inputToArray = input.toCharArray();
int startIndex=0;
int indexFromEnd = inputToArray.length-1;
while(startIndex<inputToArray.length)
{
int presentIndex=-1;
boolean indexToUsed = true;
while((presentIndex=isPresent(inputToArray,startIndex,indexFromEnd))>0)
{
if(isPalindrome(inputToArray,startIndex,presentIndex))
{
out.add(input.substring(startIndex,presentIndex+1));
indexToUsed=false;
startIndex = presentIndex;
break;
}
else
{
indexFromEnd=presentIndex-1;
}
}

if(indexToUsed)
{
out.add(String.valueOf(inputToArray[startIndex]));

}

++startIndex;
indexFromEnd=inputToArray.length-1;

}
}

//To check whether string from given range is palindrome or not
private static boolean isPalindrome(char[] inputToArray, int startIndex,
int presentIndex) {

while(startIndex<presentIndex)
{
if(inputToArray[startIndex]==inputToArray[presentIndex])
{
++startIndex;
--presentIndex;
}
else
return false;
}
return true;
}

//return the first occurrence of the startIndex character from indexFromEnd
private static int isPresent(char[] inputToArray, int startIndex,
int indexFromEnd) {

for(int i=indexFromEnd;i>startIndex;i--)
{
if(inputToArray[i]==inputToArray[startIndex])
return i;
}

return -1;
}




}
</pre><pre title="CodeMonkey79135" input="yes">
</pre>

this code take O(n^2)..

You are returning a -1 in a method that is designed to return boolean??? Also, you're while loop doesn't make any sense --> what is this : while(startIndexstartIndex;i--)

You should be able to do this using divide-and-conquer approach. The solution to this problem is similar to the solution to the divide-and-conquer approach to the maximum sum subset problem (find a consecutive subset of an array that gives the maximum sum).

The algorithm goes like this:
- find the longest possible palindromes from the left half
- find the longest possible palindromes from the right half
- look at the two results and see if there is an overlapping palindrome between the two halves...if there is, combine the two palindromes into one

if there is only one element, add it to data structure you're using to store splits (because one element is a palindrome)

the divide portion alone will take O(log n) and the combine step at the very end can at worst go through n elements, giving O( n log n )

My thought is to store the substrings in two rounds:
1. from left to right, store all substrings like (leftindex, rightindex) = hash(substring)
2. from right to left, store all substrings like (rightindex, leftindex) = hash(substring)
3. And then compare these two n^2 arrays in length order.
for 1-3 steps you can consider the cost as O(n^2), but in fact it doesn's include the cost of hash().

f[i] = minimum number of palindrome can be made from str[0,...,i]
f[i] = 1 + min(f[k]), where 0 <= k < i and str[k+1,...,i] is a palindrome.
let len=strlen(str), then the answer is f[len-1].