A string of characters is a palindrome if the sequence is the same read forward

Question

A string of characters is a palindrome if the sequence is the same read forward as backward. In this question you will solve some problems related to palindrome strings. In the following question, find the appropriate recursion and pseudocode, describe the algorithm and analyze its running time.

Given a string, we want to delete its characters by deleting a substring which is a palindrome in each iteration. Note, that a single character is a palindrome of length 1. After deleting a substring the remaining parts are concatenated. Find the minimum number of such deletions to delete the entire string. For example, the string ’23456542’ can be deleted in two iterations. First, delete ’45654’, then what is remaining is ’232’ which is deleted in the second iteration.

Explanation / Answer

Hello Student!

I am happy to help you!

So, in this question we need to delete the string in minimum number of steps by removing the palindromes. Now, what we can do - The first thing that will strike in our mind is.. everytime we delete the largest palindrome in the string will do the work. This type of approaches is considered to be greedy technique. It will not work optimally for many cases. Why?

Consider 12343223321 Palindromes that are there {23432, 3223, 22, 33 and individual string} If we apply the greedy technique we will remove 23432 string will become 123321 and it is a palindrome So two steps.

Now, if we consider to remove 3223 then string becomes 1234321 It is also a palindrome. It also takes two steps. Therefore we cannot apply a greedy technique.

What we can do? we will go for a dp solution.

Consider a two dimensional dp matrix i.e. strDel

strDel[i][j] consists the minimum number of steps it takes to delete string(i,j)

First case - Each character deleted individually of the substring (i,j) and call itself - (i+1, j)

Second case - Iterate over all the occurence in the right side, consider there is an index k ( i < k < j ) then the occurence can be divided to (i+1, k-1) and (k+1, j). We would be able to reach the solution (i+1, k-1) easily by deleting the same character.

A special case, if first two char are same subproblem becoms (i+2,j)

Pseudo Code :

minStepsToDel(str, n)

strDel[n+1][n+1]

for len = 0 : N

for i = 0, j = len-1 : N

if len == 1

strDel[i][j] = 1;

else

strDel[i][j] = 1 + steDel[i+1][j];

if str[i] == str[i+1]

strDel[i][j] = min(1+strDel[i+2][j],strDel[i][j]);

for (int K = i + 2; K <= j; K++)

if (str[i] == str[K])

strDel[i][j] = min(strDel[i+1][K-1] + strDel[K+1][j],strDel[i][j]);

end

end

return strDel[0][n-1]

Time complexity = O(n^3)

Thank you. Feel free to ask anything. If you like the answer. Please upvote it. It means a lot. Thank you again.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.