Count Palindromic Subsequences - II

The basic idea is to find all the subsequences of the string and check whether they are palindrome or not. For each character of the string we have two choices with us:

1. Include it in the current sequence.
2. Exclude it in the current sequence.

We also use a set to store the distinct subsequences and print the size of the set minus 1 (empty subsequence).

Here is the algorithm:

1. Create an unordered set (say, ‘ST’) to store the distinct subsequences.
2. Call the function HELPER to find the subsequences.
3. Return the size of ‘ST’ minus 1.

HELPER(‘S’, ‘IDX’, ‘ST’, ‘CURR’)   (where ‘S’ is the given string, ‘IDX’ is the current index, ‘ST’ is the set, ‘CURR’ is the current subsequence which is initialized to “”).

1. Base case:
   • Check if ‘IDX’ is the size of the ‘S’.
     • Check if ‘CURR’ is a palindrome.
       • Insert ‘CURR’ in ‘S’.
     • Return.
2. Call the HELPER function recursively by excluding the current character.

Similarly, call the HELPER function again by including the current character (‘CURR’ + ‘S[IDX]’).

The basic idea is to store the results of the recursive calls to avoid repetition. We can memorize the results of our function calls in an array (say, ‘DP’). We also use an extra array (say, ‘PREV’ and ‘NEXT’) to store the indexes of the characters to avoid duplication of subsequences. Two cases exist during recursive calls:

Let there be two indices, ‘i’ and ‘j’, where ‘i’ and ‘j’ are any subsequence’s first and last indices. Let ‘LEFT’ be the next index of ‘ith’ character and ‘RIGHT’ be the previous ‘jth’ character index.

1. If ‘S[i]’ is equal to ‘S[j]’
   • We add the value of the recursive call (‘i’ + 1, ‘j’ - 1) twice to the result as we can add ‘ith’ and ‘jth’ character to every palindrome that exists between ‘i’ + 1 to ‘j’ - 1.
   • If ‘LEFT’ is equal to ‘RIGHT’ (“a..a..a”), we add 1 to the count as we can get a palindrome (“aa”).
   • If ‘LEFT’ is smaller than ‘RIGHT’, we need to subtract the value of the recursive call (‘i’ + 1, ‘j’ - 1).
   • Else, add 2 to the count. (“a….a” palindrome “a”, “aa”).
2. If ‘S[i]’ is not equal to ‘S[j]’, we simply have two choices with us by excluding the ‘ith’ character or excluding the ‘jth’ character. So, there will be two recursive calls, i.e., (‘i’, ‘j’ - 1) + (‘i’ + 1, ‘j’). We also need to subtract the value of (‘i’ + 1, ‘j’ - 1) recursive call to avoid adding the count twice.

Here is the algorithm :
 

1. Create two unordered maps (say, ‘nextMAP’ and ‘prevMAP’) to store the index of the character.
2. Create two arrays (say, ‘NEXT’ and ‘PREV’) of size ‘N’ to store the last occurrence from starting for each character.
3. Run a loop from 0 to ‘N’ (say, iterator ‘i’).
   • Check if ‘S[i]’ is present in ‘prevMAP’.
     • Update ‘PREV[i]’ to ‘prevMAP[S[i]]’.
   • Else
     • Update ‘PREV[i]’ to -1.
   • Update ‘prevMAP[S[i]]’ to ‘i’.
4. Similarly, update ‘naxtMAP’, which stores the last occurrence from the last for each character by running a loop from ‘N’ - 1 to 0.
5. Create an array (say, ‘DP’) to store the recursive calls and initialize it with -1.
6. Call the function HELPER to count the number of distinct palindromic subsequences.
    

HELPER(‘S’, ‘i’, ‘j’, ‘PREV’, ‘NEXT’, ‘DP’)  (where ‘S’ is the given string, ‘i’ and ‘j’ is the first and last index of the current subsequence, ‘PREV’ and ‘NEXT’ are the array that stores index and ‘DP’ is the array to store results of function calls).
 

1. Base case:
   • Check if ‘i’ is greater than ‘j’.
     • Return 0.
   • Check if ‘i’ is equal to ‘j’.
     • Return 1.
   • Check if ‘DP[i][j]’ is not equal to -1.  (Result is present in ‘DP’).
     • Return ‘DP[i][j]’.
2. Create a variable (say, ‘CNT’) to store the count of palindromic subsequences.
3. Check if ‘S[i]’ is equal to ‘S[j]’.
   • Call the HELPER function by updating ‘i’ and ‘j’ to (‘i’ + 1, ‘j’ - 1) and the value returned by the function to ‘CNT’ after multiplying it by 2.
   • Create two variables (say, ‘LEFT’ and ‘RIGHT’) to store the next index of the first character and previous index of the last character and initialize them with ‘NEXT[i]’ and ‘PREV[j]’, respectively.
   • Check if ‘LEFT’ is smaller than ‘RIGHT’.
     • Decrease ‘CNT’ by the value returned by the recursive call of function HELPER by updating ‘i’ and ‘j’ to (‘LEFT’ + 1, ‘RIGHT’ - 1).
   • Else if ‘LEFT’ is equal to ‘RIGHT’.
     • Increment ‘CNT’ by 1.
   • Else,
     • Increase ‘CNT’ by adding 2 to it.
4. Else,
   • Call the HELPER function three times by updating ‘i’ and ‘j’ to (‘i’ + 1,’j’), (‘i’, ‘j’ + 1), and (‘i’ + 1, ‘j’ - 1).
5. Memoize the result by updating ‘DP[i][j]’ to ‘CNT’ and returning it.

The idea is similar to the previous approach. In this approach, we use an iterative way to store the count of distinct palindromic subsequences. Like the previous approach, we will create two unordered maps to store the last indices of each character and two arrays to store the previous and next indices for the current character. We also create a ‘DP’ array where ‘DP[i][j]’ represents the count of distinct palindromic subsequences from index ‘i’ to ‘j’. The conditions will be the same as the previous approach.

Here is the algorithm :
 

1. Create two unordered maps (say, ‘nextMAP’ and ‘prevMAP’) to store the index of the character.
2. Create two arrays (say, ‘NEXT’ and ‘PREV’) of size ‘N’ to store the last occurrence from starting for each character.
3. Fill the array ‘NEXT’ and ‘PREV’ similarly to the previous approach.
4. Create an array (say, ‘DP’) to store the count and initialize it with 0.
5. Run a loop from 0 to ‘N’ - 1 (say, iterator ‘i’).
   • Update ‘DP[i][i]’ to 1. (Same character is palindrome).
6. Run a loop from 2 to ‘N’ (say, iterator ‘l’).
   • Run a loop from 0 to ‘N’ - ‘l’ + 1.
     • Create a variable (say, ‘j’) and initialize it with ‘i’ + ‘l’ - 1.
     • Check if ‘S[i]’ is equal to ‘S[j]’
       • Update ‘DP[i][j]’ with ‘DP[i + 1][j - 1]’ multiplied with 2. (according to condition in previous approach).
       • Create two variables (say, ‘LEFT’ and ‘RIGHT’) and initialize them with ‘NEXT[i]’ and ‘PREV[j]’, respectively.
       • Check if ‘LEFT’ is smaller than ‘RIGHT’.
         • Update ‘DP[i][j]’ by subtracting ‘DP[LEFT + 1][RIGHT - 1]’.
       • Else check if ‘LEFT’ is equal to ‘RIGHT’.
         • Increment ‘DP[i][j]’ by 1.
       • Else
         • Increment ‘DP[i][j]’ by 2.
     • Else,
       • Update ‘DP[i][j]’ by adding ‘DP[i + 1][j]’ and ‘DP[i][j - 1]’ and subtracting ‘DP[i + 1][j - 1]’.
7. Return ‘DP[0][N - 1]’.