**A string can be partitioned into some substrings, such that each substring is a palindrome. For example, there are a few strategies to split the string “abbab” into palindrome substrings, such as: “abba”|”b”, “a”|”b”|”bab” and “a”|”bb”|”a”|”b”.**

__Problem:__
Given a string

*str*, please get the minimal numbers of splits to partition it into palindromes. The minimal number of splits to partition the string “abbab” into a set of palindromes is 1.

**This is a typical problem which can be solved by dynamic programming. We have two strategies to analyze and solve this problem**

__Analysis:__

*Solution 1: Split at any space between two characters*
Given a substring of

*str*, starting from the index*i*and ending at the index*j*(denoted as*str*[*i*:*j*]), we define a function*f*(*i*,*j*) to denote the minimal number of splits to partition the substring*str*[*i*:*j*] into a set of palindromes. If the substring is a palindrome itself, we don’t have to split so*f*(*i*,*j*) is 0. If the substring is not a palindrome, the substring is split between two characters*k*and*k*+1.*f*(*i*,*j*)=*f*(*i*,*k*)+*f*(*k*+1,*j*)+1 under such conditions. Therefore,*f*(*i*,*j*) can be defined with the following equation:
The value of

*f*(0,*n*-1) is the value of the minimal number of splits to partition*str*into palindromes, if*n*is the length of*str*.
If the equation is calculated recursively, its complexity
grows exponentially with the length

*n*. A better choice is to calculate in bottom-up order with a 2D matrix with size*n*×*n*. The following C++ code implements this solution:
int minSplit_1(const
string& str)

{

int length = str.size();

int* split = new int[length * length];

for(int i = 0; i <
length; ++i)

split[i * length + i] = 0;

for(int i = 1; i <
length; ++i)

{

for(int j = length -
i; j > 0; --j)

{

int row = length - i - j;

int col = row + i;

if(isPalindrome(str, row, col))

{

split[row * length + col] = 0;

}

else

{

int min = 0x7FFFFFFF;

for(int
k = row; k < col; ++k)

{

int temp1 = split[row * length + k];

int temp2 = split[(k + 1) * length +
col];

if(min
> temp1 + temp2 + 1)

min = temp1 + temp2 +
1;

}

split[row * length + col] = min;

}

}

}

int minSplit = split[length - 1];

delete[] split;

return minSplit;

}

*Solution 2: Split only before a palindrome*

We split the string

*str*with another strategy. Given a substring ending at the index*i*,*str*[0, i], we do not have to split if the substring is a palindrome itself. Otherwise it is split between two characters at index*j*and*j*+1 only if the substring*str*[*j*+1,*i*] is a palindrome. Therefore, an equation*f*(*i*) can be defined as the following:
The value of

*f*(*n*-1) is the value of the minimal number of splits to partition*str*into palindromes, if*n*is the length of*str*.
We could utilize a 1D array to solve this equation in
bottom-up order, as listed in the following code:

int minSplit_2(const
string& str)

{

int length = str.size();

int* split = new int[length];

for(int i = 0; i <
length; ++i)

split[i] = i;

for(int i = 1; i <
length; ++i)

{

if(isPalindrome(str, 0, i))

{

split[i] = 0;

continue;

}

for(int j = 0; j <
i; ++j)

{

if(isPalindrome(str, j + 1, i) && split[i]
> split[j] + 1)

split[i] = split[j] + 1;

}

}

int minSplit = split[length - 1];

delete[] split;

return minSplit;

}

*Optimization to verify palindromes:*

Usually it costs O(

*n*) time to check whether a string with length*n*is a palindrome, and the typical implementation looks like the following code:
bool isPalindrome(const
string& str, int begin, int end)

{

for(int i = begin; i
< end - (i - begin); ++i)

{

if(str[i] != str[end - (i - begin)])

return false;

}

return true;

}

Both solutions above cost O(

*n*^{3}) time. The first solution contains three nesting for-loops. The function isPalindrome is inside two nesting for-loops.
If we could reduce the cost of isPalindrome to O(1), the time
complexity of the second solution would be O(

*n*^{2}).
Notice that the substring

*str*[*i*,*j*] is a palindrome only if the characters at index*i*and*j*, and*str*[*i*+1,*j*-1] is also a palindrome. We could build a 2D table accordingly to store whether every substring of*str*is a palindrome or not during the preprocessing. With such a table, the function isPalindrome can verify the substring*str*[*i*,*j*] in O(1) time.
More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

can u give a code for printing top view of binary tree ?

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteA program is like these ,

ReplyDelete5 ababab

In this program we have to check the string is palindrome or not by using number means 5 is the

number then go from left to right 5 character and again right to left upto 5 th character and print the total of palindrome count

In this program it is 2 palindrome string

Can you send me the solution on my mail

niksy@ymail.com

Check this c# interview questions @ http://skillgun.com

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteHello There,

ReplyDeleteMinimal Number of Palindromes on a String being contrived to exist for many projects simply so it can be run will be the first to hit the wall, but those projects where the functions to make existing transactions cheaper in real world applications will find the elusive real world demand.

I recently attended the AWS Summit London 2018. During the afternoon session about "Open Source at AWS" there were some resources mentioned for persuading your company that open source can be a great benefit to them.

Unfortunately this wasn't one of the slide sets which has been made available after the event.

Follow my new blog if you interested in just tag along me in any social media platforms!

Cheers,

Preethi.

Hello There,

ReplyDeleteYour writing shines like gold! There is no room for gibberish here clearly. You nailed it in #topic!

I will have the mp3 files my customer buys on a wordpress page and a cart will direct them to that page. AWS Training USA .If I want the mp3 files to be downloaded by the customer is there any reason to protect them except to keep them from being indexed by a search engine? Do I need to have a key or do a get operation other than have server-side encryption in S3?

Very useful article, if I run into challenges along the way, I will share them here.

Grazie,

Preethi.

Hi Bru,

ReplyDeleteSuch vivid info on the No. 43 - Minimal Number of Palindromes on a String

Flabbergasted! Thank you for making the read a smooth sail!

The Make Public function in S3 is perfectly working these past few months and years I should say. AWS Tutorial

Just last week, we are experiencing failure in the "Make Public" function. Once I successfully upload a folder (with multiple files) then Make Public the uploaded files, the notification below shows Failure

Anyways great write up, your efforts are much appreciated.

MuchasGracias,

Irene Hynes

Hiya,

ReplyDeleteJeez oh man,while I applaud for your writing , it’s just so damn straight to the point No. 43 - Minimal Number of Palindromes on a String.

I am preparing for AWS Solutions Architect Associate exam. Signed up for AWS free tier and wanted to do a hands-on session related to VPC. Appears, AWS free tier does not allow it now. What options exist to fulfill the hands-on requirements? AWS Training

Very useful post !everyone should learn and use it during their learning path.

Best Regards,

Ajeeth