All panlindromic subsequence.

general
,
1

here is a pseudo code for counting all palindromic subsequence of a given string :

enter code here
if i == j
return 1

Else if (str[i] == str[j)]
return   countPS(i+1, j) + countPS(i, j-1) + 1;

else
return countPS(i+1, j) + countPS(i, j-1) - countPS(i+1, j-1)

i couldn’t understand that , when first and last characters are equal why we do not subtract -countPS(i+1, j-1)

as we did when when 1st and last are not same. ?

source : Count All Palindromic Subsequence in a given String - GeeksforGeeks

Can anyone please explain it ?

1 Like