Count Different Palindromic Subsequences solution and explanation
Google
9 more videos on this problem
LeetCode 730. Count Different Palindromic Subsequences Explanation and Solutionhappygirlzt · 17:55 · 8K views
730. Count Different Palindromic Subsequences (Leetcode Hard)Programming Live with Larry · 1:13:33 · 2K views
LeetCode 730. Count Different Palindromic Subsequences 中文解法 Chinese Versionhappygirlzt · 18:46 · 872 views
小Z解题 | LeeCode 730 Count Different Palindromic SubsequencescoderZ · 32:48 · 405 views
Leetcode 730. Count Different Palindromic SubsequencesAlgorithms for Big Bucks · 9:51 · 367 views
LeetCode 730: Count Different Palindromic SubsequencesAlitaCode · 31:06 · 128 views
730 Count Different Palindromic SubsequencesJeremy Huang · 20:22 · 111 views
730 count different palindromic subsequencesJimmy Wang · 3:36 · 83 views
Leetcode 0730. Count Different Palindromic SubsequencesFearless Learner · 12:37 · 40 views
No Sound Leetcode 730: Count Different Palindromic SubsequencesExtremeProgrammer · 5:13 · 18 views
The 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 109 + 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 a1, a2, ... and b1, b2, ... are different if there is some i for which ai != bi.
Example 1:
Input: s = "bccb" Output: 6 Explanation: The 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', 'bccb'. Note that 'bcb' is counted only once, even though it occurs twice.
Example 2:
Input: s = "abcdabcdabcdabcdabcdabcdabcdabcddcbadcbadcbadcbadcbadcbadcbadcba" Output: 104860361 Explanation: There are 3104860382 different non-empty palindromic subsequences, which is 104860361 modulo 109 + 7.
Constraints:
1 <= s.length <= 1000s[i]is either'a','b','c', or'd'.
Approach overview
Problem Overview: Given a string s, count how many different non‑empty palindromic subsequences exist. A subsequence can skip characters, but duplicates must only be counted once. The result is returned modulo 1e9 + 7.
Approach 1: Brute Force Subsequence Generation (Exponential)
Generate every possible subsequence using recursion or bitmasking, then check whether each subsequence is a palindrome. Store palindromes in a hash set to remove duplicates. This approach explores 2^n subsequences and performs a palindrome check for each candidate. Time complexity is O(2^n * n) with O(2^n) space for storing subsequences. It demonstrates the definition of subsequences but quickly becomes infeasible for strings longer than ~20 characters.
Approach 2: Dynamic Programming with Boundary Matching (O(n^2))
Use a 2D DP table where dp[i][j] represents the number of distinct palindromic subsequences inside substring s[i..j]. When characters at both ends match (s[i] == s[j]), new palindromes can be formed by wrapping existing subsequences between them. The tricky part is avoiding duplicates. Track the next and previous occurrences of the same character inside the substring to determine whether to add 2 * dp[i+1][j-1] + 2, 2 * dp[i+1][j-1] + 1, or subtract overlapping counts.
This duplicate handling ensures each palindrome is counted exactly once. The algorithm iterates over substring lengths and fills the DP table bottom‑up. Time complexity is O(n^2) because each substring pair is processed once, and space complexity is O(n^2) for the DP table. This method relies heavily on concepts from dynamic programming and substring analysis in string problems.
Recommended for interviews: The dynamic programming approach is the expected solution. Interviewers want to see that you recognize overlapping subproblems and handle duplicate palindromes correctly using previous/next character positions. Brute force shows understanding of subsequences, but the DP solution demonstrates real algorithmic skill.
Approach 1: Dynamic Programming Approach
This approach leverages dynamic programming to count the number of distinct palindromic subsequences in a string efficiently. The main idea is to use a 2D array dp[i][j] where each element represents the number of distinct palindromic subsequences in the substring s[i...j]. We fill this table using the following rules:
- If
s[i] == s[j], thendp[i][j] = dp[i+1][j] + dp[i][j-1] + 1(consider subsequences excluding one of the fixed characters and including both of them). - If
s[i] != s[j], thendp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1](subtract to remove the double-counted subsequences).
dp[0][n-1], where n is the length of the string s.MOD = 1000000007
def countPalindromicSubsequences(s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = 2 * dp[i + 1][j - 1]
left = i + 1
right = j - 1
while left <= right and s[left] != s[j]:
left += 1
while left <= right and s[right] != s[j]:
right -= 1
if left > right:
dp[i][j] += 2
elif left == right:
dp[i][j] += 1
else:
dp[i][j] -= dp[left + 1][right - 1]
else:
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1]
dp[i][j] = (dp[i][j] % MOD + MOD) % MOD
return dp[0][n - 1]
s = "bccb"
print(countPalindromicSubsequences(s))public class Solution {
static final int MOD = 1000000007;
public int countPalindromicSubsequences(String s) {
int n = s.length();
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int length = 2; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1;
if (s.charAt(i) == s.charAt(j)) {
dp[i][j] = 2 * dp[i + 1][j - 1];
int left = i + 1, right = j - 1;
while (left <= right && s.charAt(left) != s.charAt(j)) left++;
while (left <= right && s.charAt(right) != s.charAt(j)) right--;
if (left > right) {
dp[i][j] += 2;
} else if (left == right) {
dp[i][j] += 1;
} else {
dp[i][j] -= dp[left + 1][right - 1];
}
} else {
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
}
dp[i][j] = (dp[i][j] % MOD + MOD) % MOD;
}
}
return dp[0][n - 1];
}
public static void main(String[] args) {
Solution solution = new Solution();
String s = "bccb";
System.out.println(solution.countPalindromicSubsequences(s));
}
}#include <iostream>
#include <vector>
using namespace std;
#define MOD 1000000007
int countPalindromicSubsequences(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int length = 2; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1;
if (s[i] == s[j]) {
dp[i][j] = 2 * dp[i + 1][j - 1];
int left = i + 1, right = j - 1;
while (left <= right && s[left] != s[j]) left++;
while (left <= right && s[right] != s[j]) right--;
if (left > right) {
dp[i][j] += 2;
} else if (left == right) {
dp[i][j] += 1;
} else {
dp[i][j] -= dp[left + 1][right - 1];
}
} else {
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
}
dp[i][j] = (dp[i][j] % MOD + MOD) % MOD;
}
}
return dp[0][n - 1];
}
int main() {
string s = "bccb";
cout << countPalindromicSubsequences(s) << endl;
return 0;
}const MOD = 1000000007;
function countPalindromicSubsequences(s) {
const n = s.length;
const dp = Array.from(Array(n), () => Array(n).fill(0));
for (let i = 0; i < n; i++) dp[i][i] = 1;
for (let length = 2; length <= n; length++) {
for (let i = 0; i <= n - length; i++) {
const j = i + length - 1;
if (s[i] === s[j]) {
dp[i][j] = 2 * dp[i + 1][j - 1];
let left = i + 1, right = j - 1;
while (left <= right && s[left] !== s[j]) left++;
while (left <= right && s[right] !== s[j]) right--;
if (left > right) {
dp[i][j] += 2;
} else if (left === right) {
dp[i][j] += 1;
} else {
dp[i][j] -= dp[left + 1][right - 1];
}
} else {
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
}
dp[i][j] = (dp[i][j] % MOD + MOD) % MOD;
}
}
return dp[0][n - 1];
}
const s = 'bccb';
console.log(countPalindromicSubsequences(s));#include <stdio.h>
#define MOD 1000000007
int countPalindromicSubsequences(char* s) {
int n = strlen(s);
int dp[n][n];
memset(dp, 0, sizeof(dp));
for (int i = 0; i < n; i++) dp[i][i] = 1;
for (int length = 2; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1;
if (s[i] == s[j]) {
dp[i][j] = 2 * dp[i + 1][j - 1];
int left = i + 1, right = j - 1;
while (left <= right && s[left] != s[j]) left++;
while (left <= right && s[right] != s[j]) right--;
if (left > right) {
dp[i][j] += 2;
} else if (left == right) {
dp[i][j] += 1;
} else {
dp[i][j] -= dp[left + 1][right - 1];
}
} else {
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1];
}
dp[i][j] = (dp[i][j] % MOD + MOD) % MOD;
}
}
return dp[0][n - 1];
}
int main() {
char s[] = "bccb";
printf("%d\n", countPalindromicSubsequences(s));
return 0;
}using System;
public class Solution {
const int MOD = 1000000007;
public int CountPalindromicSubsequences(string s) {
int n = s.Length;
int[,] dp = new int[n, n];
for (int i = 0; i < n; i++) dp[i, i] = 1;
for (int length = 2; length <= n; length++)
{
for (int i = 0; i <= n - length; i++)
{
int j = i + length - 1;
if (s[i] == s[j])
{
dp[i, j] = 2 * dp[i + 1, j - 1];
int left = i + 1, right = j - 1;
while (left <= right && s[left] != s[j]) left++;
while (left <= right && s[right] != s[j]) right--;
if (left > right)
{
dp[i, j] += 2;
}
else if (left == right)
{
dp[i, j] += 1;
}
else
{
dp[i, j] -= dp[left + 1, right - 1];
}
}
else
{
dp[i, j] = dp[i + 1, j] + dp[i, j - 1] - dp[i + 1, j - 1];
}
dp[i, j] = (dp[i, j] % MOD + MOD) % MOD;
}
}
return dp[0, n - 1];
}
public static void Main(string[] args)
{
Solution solution = new Solution();
string s = "bccb";
Console.WriteLine(solution.CountPalindromicSubsequences(s));
}
}Implementing the approach in Python, this code defines a method that initializes and iteratively fills a 2D list (dp) to calculate the desired result. The Python solution closely mirrors the logic and flow of the C and Java solutions with added Pythonic syntax.
Time Complexity: O(n^2).
Space Complexity: O(n^2).
Approach 2: Default Approach
func countPalindromicSubsequences(s string) int {
mod := int(1e9) + 7
n := len(s)
dp := make([][][]int, n)
for i := range dp {
dp[i] = make([][]int, n)
for j := range dp[i] {
dp[i][j] = make([]int, 4)
}
}
for i, c := range s {
dp[i][i][c-'a'] = 1
}
for l := 2; l <= n; l++ {
for i := 0; i+l <= n; i++ {
j := i + l - 1
for _, c := range [4]byte{'a', 'b', 'c', 'd'} {
k := int(c - 'a')
if s[i] == c && s[j] == c {
dp[i][j][k] = 2 + (dp[i+1][j-1][0]+dp[i+1][j-1][1]+dp[i+1][j-1][2]+dp[i+1][j-1][3])%mod
} else if s[i] == c {
dp[i][j][k] = dp[i][j-1][k]
} else if s[j] == c {
dp[i][j][k] = dp[i+1][j][k]
} else {
dp[i][j][k] = dp[i+1][j-1][k]
}
}
}
}
ans := 0
for _, v := range dp[0][n-1] {
ans += v
}
return ans % mod
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(n^2). |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subsequence Generation | O(2^n * n) | O(2^n) | Only for learning subsequence generation or very small strings |
| Dynamic Programming with Duplicate Control | O(n^2) | O(n^2) | General solution for counting distinct palindromic subsequences efficiently |
Frequently asked questions
Is Count Different Palindromic Subsequences easy or hard?
The problem is classified as Hard on LeetCode. The challenge comes from counting only distinct palindromic subsequences while avoiding duplicates, which requires careful dynamic programming transitions and tracking repeated characters.
Count Different Palindromic Subsequences Python/Java solution
Implement the O(n^2) dynamic programming approach using a 2D DP array and modular arithmetic (1e9+7). The same logic works in Python, Java, C++, C#, and JavaScript by iterating over substring lengths and applying the duplicate-handling rules when boundary characters match.
How to solve Count Different Palindromic Subsequences in O(n^2)?
Build a DP table where dp[i][j] stores the number of distinct palindromic subsequences in s[i..j]. If s[i] != s[j], combine results from dp[i+1][j] and dp[i][j-1] while subtracting overlap. If s[i] == s[j], expand inner palindromes and adjust counts using the next and previous occurrences of that character to avoid duplicates.
What is the best approach for Count Different Palindromic Subsequences?
The optimal solution uses dynamic programming on substrings. Define dp[i][j] as the number of distinct palindromic subsequences inside s[i..j]. When the boundary characters match, wrap existing subsequences and carefully handle duplicates using the next and previous occurrences of the same character. This runs in O(n^2) time and O(n^2) space.
Is Count Different Palindromic Subsequences asked at Google/Amazon/Meta?
Variants of this problem appear in interviews at companies that emphasize dynamic programming and string manipulation, including Google and Meta. The difficulty is considered hard because handling duplicate palindromes correctly requires careful DP transitions.
What data structure is used in Count Different Palindromic Subsequences?
The main structure is a 2D dynamic programming table storing counts for every substring. Additional arrays or pointers are often used to track the next and previous occurrences of characters so duplicate palindromes can be removed correctly.
What is the time complexity of Count Different Palindromic Subsequences?
The optimal dynamic programming solution runs in O(n^2) time because every substring pair (i, j) is processed once. Space complexity is also O(n^2) for the DP table that stores counts of palindromic subsequences for each substring.