**Objective: **

You are given a large string. You need to cut the string into chunks such that each substring that you get is a palindrome. Remember that each 1 length string is always a palindrome. You need to find the minimum number of cuts that you need to make such that each substring is a palindrome.

**Example**:

String x = "xabaay" 5 cuts makes all the substrings palindrome : x, a, b, a, a, y 4 cuts makes all the substrings palindrome : x, a, b, aa, y 3 cuts makes all the substrings palindrome : x, aba, a, y Output: 3 cuts

**Approach:**

**Using Recursion:**

We need to try all the cuts which makes all the substrings palindrome and then we will choose the minimum number of cuts required.

- Check if entire string is palindrome, if yes then return 0 ( no cuts required).
- If step 1 fails means it’s not a palindrome then split the string into two parts in every possible way (ex: String is “xaab” then all possible splits are “x, aab” , “xa, ab”, “xaa, b”) and solve these two parts recursively till substring not found to be a palindrome. Each time you make a split, add 1 to number of cuts.
- Choose the minimum cuts in step 2.
- See the diagram for more understanding.

**Time Complexity**: If there are n characters in string then n-1 cuts can be made and for every cut we two options, whether cut or not. so time complexity will be** 2 ^{(n-1)}.**

**Recursion Code:**

public int splitRecursion(String x){ | |

if(x=="" || isPalindrome(x)){ | |

// System.out.println(x); | |

return 0; | |

}else{ | |

int cuts = Integer.MAX_VALUE; | |

for (int i = 1; i <x.length() ; i++) { | |

cuts = Math.min(1+ splitRecursion(x.substring(0, i)) + splitRecursion(x.substring(i, x.length())),cuts); | |

} | |

return cuts; | |

} | |

} | |

public boolean isPalindrome(String s){ | |

int n = s.length(); | |

for (int i=0;i<(n / 2) + 1;++i) { | |

if (s.charAt(i) != s.charAt(n – i – 1)) { | |

return false; | |

} | |

} | |

return true; | |

} |

We can reduce it by dynamic programming.

**Using Dynamic Programming:**

As we have see in the diagram above many problems are solved repeatedly. So we can apply the Top-down approach.

We will use Hash Map and store the solution of sub problems. So every time we make a cut, we check whether we have already solved the sub problem by checking its entry in Hash Map, if yes then use it and if not then solve it and store it in HashMap for future use.

Now this way every problem will be solved only once. Time Complexity will be number of sub problems so it will** O(N ^{2})**.

**NOTE**: We have compared the running time of recursion and dynamic programming in the output.

**Code:**:

import java.util.HashMap; | |

public class SplitPalindrome { | |

static HashMap<String,Integer> solutions = new HashMap<String, Integer>(); | |

public int splitDP(String x){ | |

if(x=="" || isPalindrome(x)){ | |

// System.out.println(x); | |

return 0; | |

}else{ | |

int cuts = Integer.MAX_VALUE; | |

for (int i = 1; i <x.length() ; i++) { | |

int leftSolution =0; | |

int rightSolution = 0; | |

String leftPart = x.substring(0,i); | |

String rightPart = x.substring(i,x.length()); | |

if(solutions.containsKey(leftPart)){ | |

leftSolution = solutions.get(leftPart); | |

}else{ | |

leftSolution = splitDP(leftPart); | |

solutions.put(leftPart,leftSolution); | |

} | |

if(solutions.containsKey(rightPart)){ | |

rightSolution = solutions.get(rightPart); | |

}else{ | |

rightSolution = splitDP(rightPart); | |

solutions.put(rightPart,rightSolution); | |

} | |

cuts = Math.min(1+ leftSolution + rightSolution,cuts); | |

} | |

return cuts; | |

} | |

} | |

public int splitRecursion(String x){ | |

if(x=="" || isPalindrome(x)){ | |

// System.out.println(x); | |

return 0; | |

}else{ | |

int cuts = Integer.MAX_VALUE; | |

for (int i = 1; i <x.length() ; i++) { | |

cuts = Math.min(1+ splitRecursion(x.substring(0, i)) + splitRecursion(x.substring(i, x.length())),cuts); | |

} | |

return cuts; | |

} | |

} | |

public boolean isPalindrome(String s){ | |

int n = s.length(); | |

for (int i=0;i<(n / 2) + 1;++i) { | |

if (s.charAt(i) != s.charAt(n – i – 1)) { | |

return false; | |

} | |

} | |

return true; | |

} | |

public static void main(String[] args) { | |

String a = "cdcdddcdadcdcdcd"; | |

SplitPalindrome s = new SplitPalindrome(); | |

long startTime = System.currentTimeMillis(); | |

System.out.println("Recursion- Cuts Required: " + s.splitRecursion(a)); | |

long stopTime = System.currentTimeMillis(); | |

long elapsedTime = stopTime – startTime; | |

System.out.println("Recursion- Time Taken(ms): " + elapsedTime); | |

startTime = System.currentTimeMillis(); | |

System.out.println("Dynamic Programming- Cuts Required: "+ s.splitDP(a)); | |

stopTime = System.currentTimeMillis(); | |

elapsedTime = stopTime – startTime; | |

System.out.println("Dynamic Programming- Time Taken(ms): " + elapsedTime); | |

} | |

} |

**Output**:

Recursion- Cuts Required: 3 Recursion- Time Taken(ms): 345 Dynamic Programming- Cuts Required: 3 Dynamic Programming- Time Taken(ms): 2

**NOTE**: As you can see the Dynamic Programming is way faster than Recursion.