### Abinash's blog

By Abinash, 7 years ago,

Problem : The number of ways one could remove letters from a particular word so that it would become a palindrome.Two ways that differ due to order of removing letters are considered the same. And it can also be the case that no letters have to be removed to form a palindrome.

I am trying to solve this problem . But my solution gives wrong answer . Then I found a solution that works here. But don't understand the recurrence . Something like this ..

ll rec(int i, int j)
{
if(j < i) return 0;
if(i == j) return 1;
ll &ret = dp[i][j];
if(ret != -1) return ret;
if(str[i] == str[j])
return ret =  1 + rec(i+1, j) + rec(i, j-1);
else
return ret = rec(i+1, j) + rec(i, j-1) - rec(i+1, j-1);
}



I don't understand why subtract rec(i+1, j-1) ? For order of removing letters are considered the same, means we count same way 2 times that why subtract ? Please explain the recurrence , thanks in advance .

• +3

 » 7 years ago, # |   +1 I think this way is better for understanding: if(str[i] == str[j]) return ret = (1 + rec(i+1, j-1)) + (rec(i+1, j) + rec(i, j-1) - rec(i+1, j-1)); else return ret = rec(i+1, j) + rec(i, j-1) - rec(i+1, j-1); rec(i+1, j) means you remove ith character and rec(i, j+1) means you remove jth character. In both rec(i+1, j) and rec(i, j-1) you will call rec(i+1, j-1). So you count rec(i+1, j-1) twice if you don't subtract it.
•  » » 7 years ago, # ^ |   0 Thanks for your great help. Now I understand .
•  » » 7 years ago, # ^ |   0 In the first return case why do we calculate rec(i+1 , j-1) ?? Since as described it will be generated by rec(i+1, j) and rec(i, j-)...Please explain...
•  » » » 7 years ago, # ^ |   0 let the string from i to j is AAAA, i=0, j=3 . if(condition) is executed.. => char A at i=0, and char A at j=3, form palindrom so +1, => rec(i+1, j-1), calculate any palindrom that can be concatenated with above palindrom... => rec(i+1, j) + rec(i, j-1) — rec(i+1, j-1), calculate same palindroms as in 2nd step but this time not concetenate with palindrom in 1st step. Hope i am right....
•  » » 6 years ago, # ^ |   0 I'm still confused on the recurrence relation here,can you be more specific please? :(
•  » » » 6 years ago, # ^ |   0 I hope this explanation makes the solution clear to you. If there is just one character in the string, it's a palindrome. If there are more characters left in the string, you can remove character from left rec(i+1, j) or right rec(i, j-1). But in both recursions you will count rec(i+1, j-1). To avoid counting twice, we subtract it from ret. There is only one case left: when str[i] == str[j], you can keep both characters (do not remove them) and then you should call rec(i+1, j-1) to build the middle and we add one because we never count the palindrome consisting of just these two characters.