Count All Palindromic Subsequence in a given String

Problem Statement

Given a string s, count the total number of palindromic subsequences in it. A subsequence is a sequence derived by deleting some or no elements without changing the order. Since the count can be very large, return the result modulo 10^9 + 7.

Example:

• Input: s = "abcd"

• Output: 4

• Explanation: The palindromic subsequences are "a", "b", "c", "d". Each single character is a palindrome.

• Input: s = "aab"

• Output: 4

• Explanation: The palindromic subsequences are "a", "a", "b", "aa".

Noob-Friendly Explanation

Think of it like this: you have a word written on separate cards. You can pick any cards you want (keeping the order), and you want to count how many different picks give you a word that reads the same forwards and backwards.

Even picking just one card gives you a palindrome (any single letter reads the same both ways). Picking "aa" from "aab" also works. We need to count ALL such possible picks.

Approach 1: Brute Force (Recursion)

Intuition

Generate all possible subsequences and check each one if it's a palindrome. We use recursion to include or exclude each character.

Algorithm

1. Generate all subsequences using recursion (include/exclude each character).
2. For each subsequence, check if it's a palindrome.
3. Count palindromic ones.

class Solution {
    int count = 0;

    public int countPalindromicSubsequences(String s) {
        generateSubsequences(s, 0, new StringBuilder());
        return count;
    }

    private void generateSubsequences(String s, int index, StringBuilder current) {
        if (index == s.length()) {
            if (current.length() > 0 && isPalindrome(current.toString())) {
                count++;
            }
            return;
        }
        // Include current character
        current.append(s.charAt(index));
        generateSubsequences(s, index + 1, current);
        current.deleteCharAt(current.length() - 1);

        // Exclude current character
        generateSubsequences(s, index + 1, current);
    }

    private boolean isPalindrome(String str) {
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
}

Complexity Analysis

• Time Complexity: O(2^n) - We generate all 2^n subsequences, and checking palindrome takes O(n) each.
• Space Complexity: O(n) - Recursion stack depth is n.

Approach 2: Optimal (Dynamic Programming)

Intuition

We use a 2D DP table where dp[i][j] stores the count of palindromic subsequences in the substring s[i..j]. We use the inclusion-exclusion principle: count palindromes ending at both i and j, plus palindromes in s[i+1..j] and s[i..j-1], minus the overlap s[i+1..j-1] (which was counted twice).

Algorithm

1. Create dp[n][n] where dp[i][i] = 1 (each character is one palindrome).
2. For substrings of increasing length, if s[i] == s[j], then dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1. The +1 is for the new palindrome formed by pairing s[i] and s[j].
3. If s[i] != s[j], then dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] (inclusion-exclusion to avoid double counting).
4. Answer is dp[0][n-1].

class Solution {
    public int countPalindromicSubsequences(String s) {
        int n = s.length();
        long MOD = 1000000007;
        long[][] dp = new long[n][n];

        // Each single character is a palindromic subsequence
        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) % MOD;
                } else {
                    dp[i][j] = (dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] + MOD) % MOD;
                }
            }
        }

        return (int) dp[0][n - 1];
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - We fill an n×n DP table, each cell in O(1).
• Space Complexity: O(n^2) - We use an n×n 2D array.