Count the number of palindromic subsequences

We are given a string str of length N. Our task is to find the number of palindromic subsequences (need not necessarily be distinct) present in the string str. Return the answer module 10^9 + 7. 

The use of modulo arithmetic helps to keep the intermediate and final results within a manageable range and prevents integer overflow. The number 10^9 + 7 is a prime number, and using it as the modulo helps ensure that the result remains within the range of 32-bit integers (in many programming languages) while still providing a large enough space for computations.

A palindromic subsequence is a sequence of characters that reads the same forward and backward. Unlike palindromic substrings, subsequences are not required to be contiguous. For example, in the string "abca," the palindromic subsequences are "a," "b," "c," "aa," "aba," and "aca".

This problem can be solved using dynamic programming or recursive approaches.

Idea

The main idea to solve the problem of counting the number of palindromic subsequences is to use dynamic programming to iteratively calculate the count for each subsequence length. The key insight is that the count for a longer subsequence depends on the counts of smaller subsequences.

• Use dynamic programming to build a table that represents the counts of palindromic subsequences for substrings of varying lengths.
• Leverage the relationship between counts of smaller substrings to efficiently compute the count for the entire string.
• The recurrence relation captures the essence of how the count for a longer substring is related to the counts of its smaller substrings, and this relation is used to fill in the dynamic programming table.

Algorithm

1. Initialize a 2D array to store counts for subproblems. dp[i][j] will represent the count of palindromic subsequences in the substring from index i to index j.
2. Initialize the base cases: Set dp[i][i] to 1 for all single characters, as a single character is a palindrome itself.
3. Fill the dp array bottom-up:

1. Iterate through all possible substring lengths, from 2 to the length of the input string.
2. For each substring length len, iterate through all possible starting indices i.
3. Calculate j, the ending index of the current substring, based on i and len.
4. If the characters at i and j are the same, you can increment dp[i][j] based on the counts from previously computed smaller substrings, including the substring within the current one.
5. If the characters at i and j are different, you need to handle that case as well.

4. The final result will be stored in dp[0][n-1], where n is the length of the input string. This value represents the count of palindromic subsequences in the entire string.

Complexity

• Time Complexity: O(N^2), where N is the length of the string.
• Space Complexity: O(N^2), where N is the length of the string.

Code

#Java

public class CountPalindromicSubsequencesDP {

    public static int countPalindromicSubsequences(String s) {

        int n = s.length();

        // Create a 2D array to store counts of palindromic subsequences
        int[][] dp = new int[n][n];

        // All individual characters are palindromic subsequences
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }

        for (int len = 2; len <= n; len++) {

            for (int i = 0; i <= n - len; i++) {

                int j = i + len - 1;

                if (s.charAt(i) == s.charAt(j)) {

                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] + 1;

                } else {

                    dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];

                }

            }

        }

        return dp[0][n - 1];
    }


    public static void main(String[] args) {
        String s = "abcd";
        int result = countPalindromicSubsequences(s);
        System.out.println("Number of palindromic subsequences: " + result);

    }
}

Output

Number of palindromic subsequences: 4