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 ?