Count Different Palindromic Subsequences
Hard · Dynamic Programming · String · Dynamic Programming
Problem
Given a string s made of the letters 'a', 'b', 'c' and 'd', return the number of different non-empty palindromic subsequences of s, modulo 10^9 + 7.
A subsequence is obtained by deleting zero or more characters without changing the order of the rest. Two subsequences count as different only when their text differs: the same palindrome picked from different positions counts once.
Examples
Input: s = "abca" Output: 6
The different palindromes are a, b, c, aa, aba and aca.
Input: s = "aaa" Output: 3
Only a, aa and aaa can be formed.
Input: s = "bccb" Output: 6
b, c, bb, cc, bcb and bccb: the inner "c" and "cc" are not counted twice.
Constraints
- 1 <= s.length <= 1000
- Each s[i] is 'a', 'b', 'c' or 'd'
Approaches
- Baseline: count by outer letter — time O(k^2 · n^2) with k = 4, space O(k · n^2)
Follow-up
The "different" rule is what makes this hard. The use cases drop it and count subsequences by position, where plain inclusion and exclusion works, and fix the length at three, where each distinct palindrome is an outer letter and a middle letter.
Related problems
Start free on Cariara · Coding problems · System design studio
