Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Dynamic Programming — Split the String into Minimum number of Palindromes.

Objec­tive:

You are given a large string. You need to cut the string into chunks such that each sub­string that you get is a palin­drome. Remem­ber that each 1 length string is always a palin­drome. You need to find the min­i­mum num­ber of cuts that you need to make such that each sub­string is a palindrome.

Exam­ple:

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 Recur­sion:

We need to try all the cuts which makes all the sub­strings palin­drome and then we will choose the min­i­mum num­ber of cuts required.

  1. Check if entire string is palin­drome, if yes then return 0 ( no cuts required).
  2. If step 1 fails means it’s not a palin­drome then split the string into two parts in every pos­si­ble way (ex: String is “xaab” then all pos­si­ble splits are “x, aab” , “xa, ab”, “xaa, b”) and solve these two parts recur­sively till sub­string not found to be a palin­drome. Each time you make a split, add 1 to num­ber of cuts.
  3. Choose the min­i­mum cuts in step 2.
  4. See the dia­gram for more understanding.

Split Palindrome - Recursion

Time Com­plex­ity: If there are n char­ac­ters in string then n-1 cuts can be made and for every cut we two options, whether cut or not. so time com­plex­ity will be 2(n-1).

Recur­sion Code:

We can reduce it by dynamic pro­gram­ming.

Using Dynamic Programming:

As we have see in the dia­gram above many prob­lems are solved repeat­edly. So we can apply the Top-down approach.

We will use Hash Map and store the solu­tion of sub prob­lems. So every time we make a cut, we check whether we have already solved the sub prob­lem by check­ing 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 prob­lem will be solved only once. Time Com­plex­ity will be num­ber of sub prob­lems so it will O(N2).

NOTE: We have com­pared the run­ning time of recur­sion and dynamic pro­gram­ming in the output.

Com­plete Code:

Out­put:

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 Pro­gram­ming is way faster than Recursion.

You may also like...