Count Different Palindromic Subsequences - Practice Coding Problems

Count Different Palindromic Subsequences - Problem

Given a string s, return the number of different non-empty palindromic subsequences in s. Since the answer may be very large, return it modulo 10⁹ + 7.

A subsequence of a string is obtained by deleting zero or more characters from the string. A sequence is palindromic if it is equal to the sequence reversed.

Two sequences a₁, a₂, ... and b₁, b₂, ... are different if there is some i for which aᵢ ≠ bᵢ.

Input & Output

Example 1 — Basic Case

$ Input: s = "bccb"

› Output: 6

💡 Note: The different palindromic subsequences are: "b", "c", "cc", "b" (from end), "bcb", "bccb". Total count is 6.

Example 2 — Single Character

$ Input: s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba"

› Output: 104860361

💡 Note: Long string with many different characters creates exponentially many palindromic subsequences, result is modulo 10^9 + 7.

Example 3 — Repeated Characters

$ Input: s = "aaa"

› Output: 3

💡 Note: The palindromic subsequences are: "a" (appears 3 times but counted once), "aa" (appears 3 times but counted once), "aaa" (appears once). Total unique count is 3.

Constraints

1 ≤ s.length ≤ 1000
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input String

Given string with characters to analyze

Find Palindromes

Identify all unique palindromic subsequences

Count Result

Return count modulo 10^9 + 7

Key Takeaway

🎯 Key Insight: Use interval DP to systematically count palindromes while avoiding duplicates through careful boundary analysis

Asked in

G Google 15 a Amazon 12 f Facebook 8 M Microsoft 6

The key insight is to use dynamic programming on substring intervals, carefully handling character matches while avoiding double counting of duplicate palindromes. Best approach is 2D DP with O(n³) time and O(n²) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Generate All Subsequences	O(2ⁿ × n)	O(2ⁿ)	Generate all possible subsequences and count palindromic ones
2D Dynamic Programming	O(n³)	O(n²)	Bottom-up DP table to count palindromes for all substring ranges
Recursive with Memoization	O(n³)	O(n²)	Use recursion with memoization to count palindromes in substrings

Generate All Subsequences — Algorithm Steps

Generate all 2^n possible subsequences
For each subsequence, check if it's a palindrome
Count unique palindromic subsequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsequences

Use bit manipulation to create all combinations

Check Palindrome

Compare each subsequence with its reverse

Count Unique

Store unique palindromes and return count

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isPalindrome(char* str) {
    int len = strlen(str);
    for (int i = 0; i < len / 2; i++) {
        if (str[i] != str[len - 1 - i]) {
            return 0;
        }
    }
    return 1;
}

int solution(char* s) {
    const int MOD = 1000000007;
    int n = strlen(s);
    char palindromes[1000][100];
    int count = 0;
    
    // Generate all subsequences using bit manipulation
    for (int mask = 1; mask < (1 << n); mask++) {
        char subseq[100] = "";
        int idx = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subseq[idx++] = s[i];
            }
        }
        subseq[idx] = '\0';
        
        // Check if palindrome and not duplicate
        if (isPalindrome(subseq)) {
            int found = 0;
            for (int i = 0; i < count; i++) {
                if (strcmp(palindromes[i], subseq) == 0) {
                    found = 1;
                    break;
                }
            }
            if (!found) {
                strcpy(palindromes[count], subseq);
                count++;
            }
        }
    }
    
    return count % MOD;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    printf("%d\n", solution(s));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2ⁿ × n)

2^n subsequences, each taking O(n) time to check palindrome

✓ Linear Growth

Space Complexity

O(2ⁿ)

Store all subsequences to check for uniqueness

✓ Linear Space

62.0K Views

Medium Frequency

~35 min Avg. Time

1.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler