Count Palindromic Subsequences

The basic idea of this approach is to break the original problem into sub-problems. Let us assume we want to find the number of palindromic subsequences in string 's' whose length is |s|.

Now, let us define a recursive function 

count(int i, int j, string &s)

Which returns the number of palindromic subsequences in the substring [i:j] of string 's'. 

Now, consider the following steps :

1. If ('i' == 'j') then return 1 because every single character in the string is a palindrome itself.
2. If ('s[i]' == 's[j]') then we need to add the following three terms to get the count:

We can append 's[i]' and 's[j]' at the front and back respectively in any palindromic subsequence of substring [i + 1, j - 1] and generate a new palindromic subsequence i.e. add count(i + 1, j - 1, s) + 1. Note 1 is added because a pair of characters ('s[i]', 's[j]') will make a palindrome.

• And also we need to add all the palindromic subsequences containing the ith and jth element separately i.e. count(i + 1, j, s) + count(i, j - 1, s) - count(i + 1, j - 1, s). We need to subtract the count of the substring [i + 1, j - 1] as it was added twice.
• After adding all the terms from the above points, return 1 + count(i, j - 1, s) + count(i + 1, j, s).

1. Otherwise ('s[i]' != 's[j]'), since the current two characters ('s[i]' and 's[j]') can’t be added, check the rest of sub-sequences i.e. return count(i, j - 1, s) + count(i + 1, j, s) - count(i + 1, j - 1, s). Note that count(i + 1, j - 1, s) is subtracted because it was added twice.

We’ll observe that there are some redundant function calls which means that there are some overlapping subproblems. The repetition of such sub-problems suggests that we can use dynamic programming to optimize our approach.

The key idea behind a dynamic programming approach is to use memoization, i.e. we’ll save the result of our sub-problem in a matrix so that it can be used later on.

Let 'dp[i][j]' be our dynamic programming matrix to store the number of palindromic subsequences in substring [i, j] of the given string 's'. It will help us to avoid redundant function calls.

Consider the following steps:

1. Before calling the function for any valid (i, j), we will first check whether we have already a solution corresponding to the (i, j) if we have then, return the answer from the 'dp' table.
2. If ('i' == 'j') then the answer is 1 because every single character in the string is a palindrome itself.
3. If ('s[i]' == 's[j]' ) then we need to add the following three terms to get the count:

We can append 's[i]' and 's[j]' at the front and back respectively in any palindromic subsequence of substring [i + 1, j - 1] and generate a new palindromic subsequence i.e. add count(i + 1, j - 1, s) + 1. Note 1 is added because a pair of characters ('s[i]', 's[j]') will make a palindrome.

• And also we need to add all the palindromic subsequences containing the ith and jth element separately i.e. count(i + 1, j, s) + count(i, j - 1, s) - count(i + 1, j - 1, s). We need to subtract the count of the substring [i + 1, j - 1] as it was added twice.
• After adding all the terms from the above points, return 1 + count(i, j - 1, s) + count(i + 1, j, s).

1. Otherwise ('s[i]' != 's[j]'), since the current two characters ('s[i]' and 's[j]') can’t be added, check the rest of sub-sequences i.e. return count(i, j - 1, s) + count(i + 1, j, s) - count(i + 1, j - 1, s). Note that count(i + 1, j - 1, s) is subtracted because it was added twice.
2. Store the answer in the 'dp' table for later use.

The basic idea here is to use a bottom-up dynamic programming approach to solve the problem. The recursion function is discussed in the above mentioned approach.

Let 'dp[i][j]' be our dynamic programming matrix to store the number of palindromic subsequences in substring [i, j] of the given string 's'.

Now, consider the following steps :

1. Start traversing the given string using a variable 'i'.
2. Create a nested loop using a variable 'j' such that 'i' <= 'j' < |s|.
3. Now, create a variable 'len' which stores the length of substring [i, j] i.e. 'len' = 'j' - 'i' + 1.
4. If ('len' == 1), then 'dp[i][j]' = 1 because every single character in the string is a palindrome itself.
5. If ('len' == 2), then
   • If ('s[i]' == 's[j]') then 'dp[i][j]' = 3, because each subsequence will be a palindrome.
   • Else, 'dp[i][j]' = 2, two palindromes of a single character.
6. Otherwise, we can use the strategy described in approach 1 to break the problem into sub-problems.
   • If ('s[i]' == 's[j]'),  'dp[i][j]' = 1 + 'dp[i + 1][j]' + 'dp[i][j - 1]'
   • Otherwise, 'dp[i][j]' = 'dp[i + 1][j]' + 'dp[i][j - 1]' - 'dp[i + 1][j - 1]'