730. Count Different Palindromic Subsequences
Problem Description
You are given a string s consisting of characters. Your task is to count the total number of distinct non-empty palindromic subsequences that can be formed from this string.
A subsequence is a sequence that can be derived from the original string by deleting some (possibly zero) characters without changing the order of the remaining characters. For example, "ace" is a subsequence of "abcde".
A palindromic sequence reads the same forwards and backwards. For example, "aba", "aa", and "a" are palindromes.
Two subsequences are considered different if they differ as strings, that is, if they differ in at least one position of the resulting sequence. Picking the same palindrome string from different character positions of the original string counts only once.
Since the count can be very large, you need to return the result modulo 10^9 + 7.
Key Points:
- You need to find all possible palindromic subsequences (not substrings)
- Each distinct palindromic subsequence should be counted once
- The subsequences must be non-empty
- Return the count modulo
10^9 + 7
Example:
If s = "bccb", the palindromic subsequences are: "b", "c", "bb", "cc", "bcb", "bccb" - giving us a total count of 6.
How We Pick the Algorithm
Why Dynamic Programming?
This problem maps to Dynamic Programming through a short path in the full flowchart.
3D interval DP per boundary character counts distinct palindromic subsequences inside each substring modulo 1e9+7.
Open in FlowchartIntuition
When thinking about counting palindromic subsequences, we need to consider how palindromes are structured - they read the same forwards and backwards. This means that for any palindrome, the first and last characters must be the same.
The key insight is to use dynamic programming with a focus on the boundary characters. For any substring s[i...j], we can count palindromic subsequences based on what characters appear at the boundaries.
Since the problem mentions the string contains only lowercase letters (and from the solution we can see it's specifically 'a', 'b', 'c', 'd'), we can track palindromes ending with each specific character. This leads us to define our DP state as dp[i][j][k] where:
iandjrepresent the substring boundarieskrepresents which character (0 for 'a', 1 for 'b', 2 for 'c', 3 for 'd') the palindrome starts and ends with
The critical observation is how to build larger palindromes from smaller ones:
-
When
s[i] == s[j] == c(both boundaries match characterc): We can form new palindromes by:- Taking just the character
citself (count = 1) - Taking
c + c(count = 1) - Taking any palindrome from the inner substring
s[i+1...j-1]and wrapping it withcon both sides
This gives us:
dp[i][j][k] = 2 + sum(all palindromes in dp[i+1][j-1]) - Taking just the character
-
When only
s[i] == c: The palindromes ending withcmust start at positioni, so we look ats[i...j-1] -
When only
s[j] == c: The palindromes ending withcmust end at positionj, so we look ats[i+1...j] -
When neither boundary is
c: Any palindrome with charactercmust be completely contained in the inner substrings[i+1...j-1]
By building up from single characters (base case) to larger substrings, we can count all distinct palindromic subsequences. The final answer is the sum of all palindromes in the entire string s[0...n-1] for all possible ending characters.
Pattern Learn more about Dynamic Programming patterns.
Solution Approach
The solution implements a 3D dynamic programming approach to count palindromic subsequences. Let's walk through the implementation step by step:
1. Initialization:
dp = [[[0] * 4 for _ in range(n)] for _ in range(n)]
We create a 3D DP table where dp[i][j][k] stores the count of distinct palindromic subsequences in substring s[i...j] that start and end with character k (where k maps to 'a', 'b', 'c', 'd' as 0, 1, 2, 3).
2. Base Case:
for i, char in enumerate(s):
char_index = ord(char) - ord('a')
dp[i][i][char_index] = 1
Single characters are palindromes themselves. For each position i, we mark that there's exactly 1 palindrome of length 1 ending with that character.
3. Building Up Solutions:
for length in range(2, n + 1): # substring length
for start in range(n - length + 1): # starting position
end = start + length - 1 # ending position
We iterate through all possible substring lengths from 2 to n, and for each length, we consider all possible starting positions.
4. Core DP Transition:
For each substring s[i...j] and each possible character c in 'abcd':
-
Case 1:
s[i] == s[j] == cdp[start][end][char_index] = (2 + sum(dp[start + 1][end - 1])) % MODWhen both boundaries match character
c, we can form:- The single character
c(count = 1) - The double character
cc(count = 1) - Any palindrome from inner substring wrapped with
con both sides
The result is reduced modulo
10^9 + 7right away so the stored numbers stay small. - The single character
-
Case 2:
s[i] == cbuts[j] != cdp[start][end][char_index] = dp[start][end - 1][char_index]Palindromes with character
cmust start at positioni, so we exclude the last character. -
Case 3:
s[i] != cbuts[j] == cdp[start][end][char_index] = dp[start + 1][end][char_index]Palindromes with character
cmust end at positionj, so we exclude the first character. -
Case 4: Neither boundary is
cdp[start][end][char_index] = dp[start + 1][end - 1][char_index]Any palindrome with character
cmust be completely within the inner substring.
5. Final Result:
return sum(dp[0][n - 1]) % MOD
The total count is the sum of all palindromic subsequences in the entire string s[0...n-1] for all possible characters, taken modulo 10^9 + 7.
Time Complexity: O(n² × 4) = O(n²) where n is the length of the string
Space Complexity: O(n² × 4) = O(n²) for the 3D DP table
Example Walkthrough
Let's walk through a small example with s = "bccb" to illustrate the solution approach.
Step 1: Initialize the DP table
We create a 3D DP table dp[i][j][k] where indices represent:
i,j: substring boundaries (0 to 3 for our string of length 4)k: character type (0='a', 1='b', 2='c', 3='d')
Step 2: Base case - single characters
s = "b c c b" 0 1 2 3 (indices)
For each single character:
- Position 0: 'b' →
dp[0][0][1] = 1(one palindrome "b") - Position 1: 'c' →
dp[1][1][2] = 1(one palindrome "c") - Position 2: 'c' →
dp[2][2][2] = 1(one palindrome "c") - Position 3: 'b' →
dp[3][3][1] = 1(one palindrome "b")
Step 3: Build substrings of length 2
For substring "bc" (i=0, j=1):
- For character 'b': s[0]='b', s[1]='c' → only left boundary matches
dp[0][1][1] = dp[0][0][1] = 1(palindrome "b")
- For character 'c': s[0]='b', s[1]='c' → only right boundary matches
dp[0][1][2] = dp[1][1][2] = 1(palindrome "c")
For substring "cc" (i=1, j=2):
- For character 'c': s[1]='c', s[2]='c' → both boundaries match!
dp[1][2][2] = 2 + sum(dp[2][1])- Since i+1 > j-1, inner substring is empty, sum = 0
dp[1][2][2] = 2(palindromes "c" and "cc")
For substring "cb" (i=2, j=3):
- For character 'c': s[2]='c', s[3]='b' → only left boundary matches
dp[2][3][2] = dp[2][2][2] = 1(palindrome "c")
- For character 'b': s[2]='c', s[3]='b' → only right boundary matches
dp[2][3][1] = dp[3][3][1] = 1(palindrome "b")
Step 4: Build substrings of length 3
For substring "bcc" (i=0, j=2):
- For character 'b': s[0]='b', s[2]='c' → only left boundary matches
dp[0][2][1] = dp[0][1][1] = 1(palindrome "b")
- For character 'c': s[0]='b', s[2]='c' → only right boundary matches
dp[0][2][2] = dp[1][2][2] = 2(palindromes "c", "cc")
For substring "ccb" (i=1, j=3):
- For character 'c': s[1]='c', s[3]='b' → only left boundary matches
dp[1][3][2] = dp[1][2][2] = 2(palindromes "c", "cc")
- For character 'b': s[1]='c', s[3]='b' → only right boundary matches
dp[1][3][1] = dp[2][3][1] = 1(palindrome "b")
Step 5: Build substring of length 4 (entire string)
For substring "bccb" (i=0, j=3):
- For character 'b': s[0]='b', s[3]='b' → both boundaries match!
- Inner substring is "cc" (i+1=1, j-1=2)
- Sum of inner palindromes =
dp[1][2][2] = 2 dp[0][3][1] = 2 + 2 = 4(palindromes "b", "bb", "bcb", "bccb")
- For character 'c': s[0]='b', s[3]='b' → neither boundary matches
dp[0][3][2] = dp[1][2][2] = 2(palindromes "c", "cc")
Step 6: Calculate final result Total palindromic subsequences = sum of all characters for entire string:
dp[0][3][0](character 'a') = 0dp[0][3][1](character 'b') = 4dp[0][3][2](character 'c') = 2dp[0][3][3](character 'd') = 0
Total = 0 + 4 + 2 + 0 = 6
The 6 distinct palindromic subsequences are: "b", "c", "bb", "cc", "bcb", "bccb"
Solution Implementation
1class Solution:
2 def countPalindromicSubsequences(self, s: str) -> int:
3 MOD = 10**9 + 7
4 n = len(s)
5
6 # dp[i][j][char_idx] = number of distinct palindromic subsequences
7 # in s[i:j+1] that start and end with character at index char_idx
8 # where char_idx: 0='a', 1='b', 2='c', 3='d'
9 dp = [[[0] * 4 for _ in range(n)] for _ in range(n)]
10
11 # Base case: single characters are palindromes
12 for i, char in enumerate(s):
13 char_index = ord(char) - ord('a')
14 dp[i][i][char_index] = 1
15
16 # Process substrings of increasing length
17 for length in range(2, n + 1):
18 for start in range(n - length + 1):
19 end = start + length - 1
20
21 # Try each possible character as start/end of palindrome
22 for char in 'abcd':
23 char_index = ord(char) - ord('a')
24
25 if s[start] == s[end] == char:
26 # Both ends match the current character
27 # Count: "c" + "cc" + every inner palindrome wrapped as c...c
28 dp[start][end][char_index] = (2 + sum(dp[start + 1][end - 1])) % MOD
29 elif s[start] == char:
30 # Only start matches - exclude the end character
31 dp[start][end][char_index] = dp[start][end - 1][char_index]
32 elif s[end] == char:
33 # Only end matches - exclude the start character
34 dp[start][end][char_index] = dp[start + 1][end][char_index]
35 else:
36 # Neither end matches - look at inner substring
37 dp[start][end][char_index] = dp[start + 1][end - 1][char_index]
38
39 # Return total count of distinct palindromic subsequences
40 return sum(dp[0][n - 1]) % MOD
411class Solution {
2 // Modulo value for preventing integer overflow
3 private final int MOD = (int) 1e9 + 7;
4
5 /**
6 * Count distinct palindromic subsequences in a string containing only 'a', 'b', 'c', 'd'
7 * @param s Input string
8 * @return Number of distinct palindromic subsequences modulo 10^9 + 7
9 */
10 public int countPalindromicSubsequences(String s) {
11 int length = s.length();
12
13 // dp[i][j][k] represents count of distinct palindromic subsequences
14 // in substring s[i...j] that start and end with character ('a' + k)
15 long[][][] dp = new long[length][length][4];
16
17 // Base case: single character is a palindrome
18 for (int i = 0; i < length; ++i) {
19 int charIndex = s.charAt(i) - 'a';
20 dp[i][i][charIndex] = 1;
21 }
22
23 // Build dp table for increasing substring lengths
24 for (int substringLength = 2; substringLength <= length; ++substringLength) {
25 for (int startIdx = 0; startIdx + substringLength <= length; ++startIdx) {
26 int endIdx = startIdx + substringLength - 1;
27
28 // Try each character 'a' to 'd' as potential palindrome boundaries
29 for (char currentChar = 'a'; currentChar <= 'd'; ++currentChar) {
30 int charIndex = currentChar - 'a';
31
32 if (s.charAt(startIdx) == currentChar && s.charAt(endIdx) == currentChar) {
33 // Both boundaries match the current character
34 // Count includes: single char "c" (1) + double char "cc" (1) +
35 // all palindromes from inner substring wrapped by current char
36 dp[startIdx][endIdx][charIndex] = 2; // "c" and "cc"
37
38 // Add all possible palindromes from inner substring
39 for (int k = 0; k < 4; ++k) {
40 dp[startIdx][endIdx][charIndex] += dp[startIdx + 1][endIdx - 1][k];
41 }
42
43 dp[startIdx][endIdx][charIndex] %= MOD;
44 } else if (s.charAt(startIdx) == currentChar) {
45 // Only start boundary matches - exclude last character
46 dp[startIdx][endIdx][charIndex] = dp[startIdx][endIdx - 1][charIndex];
47 } else if (s.charAt(endIdx) == currentChar) {
48 // Only end boundary matches - exclude first character
49 dp[startIdx][endIdx][charIndex] = dp[startIdx + 1][endIdx][charIndex];
50 } else {
51 // Neither boundary matches - exclude both first and last characters
52 dp[startIdx][endIdx][charIndex] = dp[startIdx + 1][endIdx - 1][charIndex];
53 }
54 }
55 }
56 }
57
58 // Calculate total count by summing palindromes starting with each character
59 long totalCount = 0;
60 for (int charIndex = 0; charIndex < 4; ++charIndex) {
61 totalCount += dp[0][length - 1][charIndex];
62 }
63
64 return (int) (totalCount % MOD);
65 }
66}
671using ll = long long;
2
3class Solution {
4public:
5 int countPalindromicSubsequences(string s) {
6 const int MOD = 1e9 + 7;
7 int n = s.size();
8
9 // dp[i][j][k] = number of distinct palindromic subsequences
10 // in substring s[i...j] that start and end with character ('a' + k)
11 vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(n, vector<ll>(4, 0)));
12
13 // Base case: single character is a palindrome by itself
14 for (int i = 0; i < n; ++i) {
15 dp[i][i][s[i] - 'a'] = 1;
16 }
17
18 // Process all substrings of increasing length
19 for (int length = 2; length <= n; ++length) {
20 for (int start = 0; start + length <= n; ++start) {
21 int end = start + length - 1;
22
23 // Try each character 'a' to 'd' as potential boundary character
24 for (char ch = 'a'; ch <= 'd'; ++ch) {
25 int charIndex = ch - 'a';
26
27 if (s[start] == ch && s[end] == ch) {
28 // Both boundaries match the current character
29 // Count includes: single char 'ch', double char "ch ch",
30 // and all palindromes from inner substring wrapped by 'ch'
31 ll innerSum = 0;
32 for (int k = 0; k < 4; ++k) {
33 innerSum = (innerSum + dp[start + 1][end - 1][k]) % MOD;
34 }
35 dp[start][end][charIndex] = (2 + innerSum) % MOD;
36 }
37 else if (s[start] == ch) {
38 // Only start boundary matches
39 // Exclude the last character
40 dp[start][end][charIndex] = dp[start][end - 1][charIndex];
41 }
42 else if (s[end] == ch) {
43 // Only end boundary matches
44 // Exclude the first character
45 dp[start][end][charIndex] = dp[start + 1][end][charIndex];
46 }
47 else {
48 // Neither boundary matches current character
49 // Look for palindromes in the inner substring
50 dp[start][end][charIndex] = dp[start + 1][end - 1][charIndex];
51 }
52 }
53 }
54 }
55
56 // Sum up all distinct palindromic subsequences for the entire string
57 ll totalCount = 0;
58 for (int k = 0; k < 4; ++k) {
59 totalCount = (totalCount + dp[0][n - 1][k]) % MOD;
60 }
61
62 return static_cast<int>(totalCount % MOD);
63 }
64};
651type ll = number;
2
3function countPalindromicSubsequences(s: string): number {
4 const MOD = 1e9 + 7;
5 const n = s.length;
6
7 // dp[i][j][k] = number of distinct palindromic subsequences
8 // in substring s[i...j] that start and end with character ('a'.charCodeAt(0) + k)
9 const dp: ll[][][] = Array(n).fill(null).map(() =>
10 Array(n).fill(null).map(() =>
11 Array(4).fill(0)
12 )
13 );
14
15 // Base case: single character is a palindrome by itself
16 for (let i = 0; i < n; i++) {
17 dp[i][i][s.charCodeAt(i) - 'a'.charCodeAt(0)] = 1;
18 }
19
20 // Process all substrings of increasing length
21 for (let length = 2; length <= n; length++) {
22 for (let start = 0; start + length <= n; start++) {
23 const end = start + length - 1;
24
25 // Try each character 'a' to 'd' as potential boundary character
26 for (let ch = 'a'.charCodeAt(0); ch <= 'd'.charCodeAt(0); ch++) {
27 const charIndex = ch - 'a'.charCodeAt(0);
28
29 if (s.charCodeAt(start) === ch && s.charCodeAt(end) === ch) {
30 // Both boundaries match the current character
31 // Count includes: single char 'ch', double char "ch ch",
32 // and all palindromes from inner substring wrapped by 'ch'
33 let innerSum: ll = 0;
34 for (let k = 0; k < 4; k++) {
35 innerSum = (innerSum + dp[start + 1][end - 1][k]) % MOD;
36 }
37 dp[start][end][charIndex] = (2 + innerSum) % MOD;
38 }
39 else if (s.charCodeAt(start) === ch) {
40 // Only start boundary matches
41 // Exclude the last character
42 dp[start][end][charIndex] = dp[start][end - 1][charIndex];
43 }
44 else if (s.charCodeAt(end) === ch) {
45 // Only end boundary matches
46 // Exclude the first character
47 dp[start][end][charIndex] = dp[start + 1][end][charIndex];
48 }
49 else {
50 // Neither boundary matches current character
51 // Look for palindromes in the inner substring
52 dp[start][end][charIndex] = dp[start + 1][end - 1][charIndex];
53 }
54 }
55 }
56 }
57
58 // Sum up all distinct palindromic subsequences for the entire string
59 let totalCount: ll = 0;
60 for (let k = 0; k < 4; k++) {
61 totalCount = (totalCount + dp[0][n - 1][k]) % MOD;
62 }
63
64 return totalCount % MOD;
65}
66Time and Space Complexity
Time Complexity: O(n² × 4) = O(n²)
The algorithm uses dynamic programming with three nested loops:
- The outer loop iterates through all possible substring lengths from 2 to n:
O(n)iterations - The middle loop iterates through all possible starting positions for substrings of length l:
O(n)iterations - The inner loop iterates through all 4 possible characters ('a', 'b', 'c', 'd'):
O(4)=O(1)iterations
Within the innermost loop, the operations are mostly O(1), except for one case where sum(dp[i + 1][j - 1]) is called, which takes O(4) = O(1) time since it sums over 4 elements.
Therefore, the total time complexity is O(n × n × 4) = O(n²).
Space Complexity: O(n² × 4) = O(n²)
The algorithm uses a 3-dimensional DP table:
- First dimension represents the starting index:
npositions - Second dimension represents the ending index:
npositions - Third dimension represents the character type (a, b, c, or d):
4values
The total space required is n × n × 4 = O(n²) since 4 is a constant.
No additional significant auxiliary space is used beyond the DP table and a few variables, so the overall space complexity remains O(n²).
Pattern Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Incorrect Modulo Application
A common pitfall is applying the modulo operation only at the final return statement. The true counts grow exponentially with n, so intermediate values overflow in languages with fixed-size integers (Java, C++, TypeScript). In Python the result stays correct, but the numbers grow to hundreds of bits and every addition becomes slower.
Problem Code:
dp[start][end][char_index] = 2 + sum(dp[start + 1][end - 1])
# ... other assignments without modulo
return sum(dp[0][n - 1]) % MOD
Solution: Apply the modulo operation in the one case that adds values, as the solution does. The other three cases copy a value that is already reduced, so they need no extra modulo:
if s[start] == s[end] == char:
dp[start][end][char_index] = (2 + sum(dp[start + 1][end - 1])) % MOD
2. Reading the Empty Inner Substring for Length 2
When computing dp[start + 1][end - 1] for substrings of length 2, we get start + 1 > end - 1, which describes an empty inner substring.
What Happens in the Solution:
When length = 2, we have end = start + 1, so dp[start + 1][end - 1] is dp[end][start]. The solution never writes to cells with first index greater than second index, so this cell keeps its initial value of all zeros. That is exactly the count for an empty substring, so the solution handles this case correctly without a special branch. The pitfall appears only in variants that fill the table differently (for example, reusing memory or using a memoized recursion that does not return 0 for i > j).
Explicit Alternative: Some implementations make the empty case explicit for readability:
if s[start] == s[end] == char:
if length == 2:
# For length 2, we have two palindromes: single char and double char
dp[start][end][char_index] = 2
else:
# For longer strings, include inner palindromes
inner_sum = sum(dp[start + 1][end - 1]) % MOD
dp[start][end][char_index] = (2 + inner_sum) % MOD
3. Assumption About Character Set
The code assumes the input string contains only characters 'a', 'b', 'c', 'd'. If the string contains other characters, the solution will fail or produce incorrect results.
Problem:
for char in 'abcd': # Hard-coded character set
char_index = ord(char) - ord('a')
Solution: Either validate the input or dynamically determine the character set:
# Option 1: Validate input
unique_chars = set(s)
if not unique_chars.issubset({'a', 'b', 'c', 'd'}):
raise ValueError("String must contain only characters a, b, c, d")
# Option 2: Dynamic character set
unique_chars = sorted(set(s))
char_to_index = {char: i for i, char in enumerate(unique_chars)}
dp = [[[0] * len(unique_chars) for _ in range(n)] for _ in range(n)]
Solution with Explicit Edge Cases:
class Solution:
def countPalindromicSubsequences(self, s: str) -> int:
MOD = 10**9 + 7
n = len(s)
dp = [[[0] * 4 for _ in range(n)] for _ in range(n)]
# Base case
for i, char in enumerate(s):
char_index = ord(char) - ord('a')
dp[i][i][char_index] = 1
# Process substrings
for length in range(2, n + 1):
for start in range(n - length + 1):
end = start + length - 1
for char in 'abcd':
char_index = ord(char) - ord('a')
if s[start] == s[end] == char:
if length == 2:
dp[start][end][char_index] = 2
else:
inner_sum = sum(dp[start + 1][end - 1]) % MOD
dp[start][end][char_index] = (2 + inner_sum) % MOD
elif s[start] == char:
dp[start][end][char_index] = dp[start][end - 1][char_index]
elif s[end] == char:
dp[start][end][char_index] = dp[start + 1][end][char_index]
else:
if length > 2:
dp[start][end][char_index] = dp[start + 1][end - 1][char_index]
# else: remains 0 for length 2 when neither end matches
return sum(dp[0][n - 1]) % MOD
Ready to land your dream job?
Unlock your dream job with a 5-minute quiz for a personalized study roadmap!
Get My RoadmapWhich of the following is a good use case for backtracking?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him
Want a Structured Path to Master System Design Too? Don’t Miss This!