Count All Palindromic Subsequence in a given String

Problem Statement

Given a string, count all palindromic subsequences in it. A palindromic subsequence is a sequence that reads the same forwards and backwards and can be derived by deleting some or no characters from the original string.

Example:

• Input: "abcd"

• Output: 4

• Explanation: Palindromic subsequences are "a", "b", "c", "d"

• Input: "aab"

• Output: 4

• Explanation: Palindromic subsequences are "a", "a", "b", "aa"

• Input: "aba"

• Output: 5

• Explanation: "a", "b", "a", "aa", "aba"

Note: Single characters are palindromes. Count duplicates separately if they appear at different positions.

Approach 1: Brute Force (Generate All Subsequences)

Intuition

Generate all 2^n subsequences and check each one for palindrome property.

Algorithm

1. Generate all subsequences using recursion/bit manipulation
2. Check each subsequence if it's a palindrome
3. Count palindromic ones

public class Solution {
    private boolean isPalindrome(String s) {
        int left = 0, right = s.length() - 1;
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) return false;
            left++;
            right--;
        }
        return true;
    }
    
    public int countPalindromicSubseq(String s) {
        int n = s.length();
        int count = 0;
        int total = 1 << n;
        
        for (int mask = 1; mask < total; mask++) {
            StringBuilder subseq = new StringBuilder();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subseq.append(s.charAt(i));
                }
            }
            if (isPalindrome(subseq.toString())) {
                count++;
            }
        }
        
        return count;
    }
}

Complexity Analysis

• Time Complexity: O(2^n × n) - 2^n subsequences, O(n) palindrome check each
• Space Complexity: O(n) - For storing current subsequence

Approach 2: Optimal (Dynamic Programming)

Intuition

Let dp[i][j] represent the count of palindromic subsequences in substring s[i..j].

Recurrence Relation

1. If s[i] == s[j]:

   • dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1
   • The +1 is for the new palindrome formed by s[i] and s[j] alone

2. If s[i] != s[j]:

   • dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
   • Subtract intersection to avoid double counting

Algorithm

1. Base case: single characters are palindromes, dp[i][i] = 1
2. Fill table for increasing lengths
3. Return dp[0][n-1]

public class Solution {
    public int countPalindromicSubseq(String s) {
        int n = s.length();
        
        // dp[i][j] = count of palindromic subsequences in s[i..j]
        int[][] dp = new int[n][n];
        
        // Base case: single characters
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        
        // Fill for lengths 2 to n
        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];
    }
}

Complexity Analysis

• Time Complexity: O(n²) - Filling n² table entries
• Space Complexity: O(n²) - For the DP table

Approach 3: Count Distinct Palindromic Subsequences

Intuition

If we want to count only distinct palindromic subsequences, we need to handle duplicates.

Approach 4: Longest Palindromic Subsequence (Related)

Intuition

While counting, we might also want to find the longest palindromic subsequence.

Understanding the DP Recurrence

For s[i..j]:

Case 1: s[i] == s[j]

• dp[i+1][j]: palindromes in s[i+1..j]
• dp[i][j-1]: palindromes in s[i..j-1]
• +1: new palindrome formed by s[i] and s[j] together

Why no subtraction? Because when s[i]==s[j], any palindrome in the middle combined with s[i] and s[j] forms a new palindrome not counted before.

Case 2: s[i] != s[j]

• Add both sides but subtract intersection (double counted)

Space Optimization

Key Takeaways

1. Single characters are palindromes - base case
2. DP recurrence handles matching/non-matching endpoints differently
3. For distinct palindromes, need to handle duplicates carefully
4. The formula avoids double counting using inclusion-exclusion
5. Time complexity reduced from O(2^n) to O(n²) with DP
6. Related problems: Longest Palindromic Subsequence, Palindrome Partitioning
7. Use modular arithmetic for large counts to avoid overflow

Related Problems

1. Longest Palindromic Subsequence (LeetCode 516)
2. Count Different Palindromic Subsequences (LeetCode 730)
3. Palindrome Partitioning II (LeetCode 132)
4. Palindromic Substrings (LeetCode 647)