Count Palindromic Subsequences - Practice Coding Problems

Count Palindromic Subsequences - Problem

Given a string of digits s, return the number of palindromic subsequences of s having length 5. Since the answer may be very large, return it modulo 10⁹ + 7.

Note:

A string is palindromic if it reads the same forward and backward.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

Input & Output

Example 1 — Basic Case

$ Input: s = "103301"

› Output: 1

💡 Note: The palindromic subsequence of length 5 is "10301". We take positions 0,1,2,4,5 to get digits 1,0,3,0,1 which forms a palindrome.

Example 2 — Multiple Palindromes

$ Input: s = "1212121"

› Output: 6

💡 Note: Multiple 5-digit palindromic subsequences exist: 12121 can be formed in 6 different ways by choosing different positions of 1s and 2s.

Example 3 — No Valid Palindromes

$ Input: s = "12345"

› Output: 0

💡 Note: No palindromic subsequences of length 5 can be formed since all digits are different.

Constraints

1 ≤ s.length ≤ 1000
s consists only of digits.

Visualization

Tap to expand

Understanding the Visualization

Input String

String of digits with potential palindromic subsequences

Pattern Recognition

Find positions where palindrome pattern abcba exists

Count Result

Total number of valid 5-digit palindromic subsequences

Key Takeaway

🎯 Key Insight: Look for matching pairs of digits that can form the outer and inner layers of a 5-digit palindrome pattern

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to recognize that a 5-digit palindrome has the form abcba where the first and last digits match, and the second and fourth digits match. The optimal approach uses nested loops to find matching outer pairs, then count matching inner pairs between them. Time: O(n⁴), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Subsequences	O(n⁵)	O(1)	Generate all possible 5-character subsequences and check if palindromic
Optimized DP - Prefix/Suffix Counting	O(n)	O(n)	Use prefix and suffix digit counts to efficiently calculate palindrome combinations
Dynamic Programming - Count Triplets	O(n²)	O(n)	Count 3-character palindromic subsequences, then extend to 5-character

Brute Force - Generate All Subsequences — Algorithm Steps

Generate all 5-character subsequences
Check if each subsequence is palindromic
Count palindromic subsequences

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all 5-character subsequences

Check

Verify if palindromic (first=last, second=fourth)

Count

Count valid palindromes

Code -

solution.c — C

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

int solution(char* s) {
    const int MOD = 1000000007;
    int n = strlen(s);
    long long count = 0;
    
    // Generate all 5-character subsequences
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                for (int l = k + 1; l < n; l++) {
                    for (int m = l + 1; m < n; m++) {
                        // Check if palindrome
                        if (s[i] == s[m] && s[j] == s[l]) {
                            count = (count + 1) % MOD;
                        }
                    }
                }
            }
        }
    }
    
    return count;
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n⁵)

Five nested loops to generate all 5-character combinations

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for counters

✓ Linear Space

23.4K Views

Medium Frequency

~35 min Avg. Time

892 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

Brute Force - Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler