Skip to main content
Talentd

Count Different Palindromic Subsequences - Solution & Explanation

HardStringDynamic Programming13 min readAsked at: Uber, Google, LinkedIn +1
Practice this problem

Problem Statement

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 <= 1000
  • s[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], then dp[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], then dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] (subtract to remove the double-counted subsequences).
The result is the value in dp[0][n-1], where n is the length of the string s.

This C solution iterates through all possible substrings of the given string s and fills out a dynamic programming table dp using the rules described above. Special care is taken to handle the modulo operation for ensuring results don't overflow the integer limits. The final number of distinct palindromic subsequences is then returned as the result.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), because we are using a two-dimensional array to store results and iterating over all possible substrings.
Space Complexity: O(n^2), due to the space required for the 2D array dp.

Try this approach in the editor →

Approach 2: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming Approach

Time Complexity: O(n^2), because we are using a two-dimensional array to store results and iterating over all possible substrings.
Space Complexity: O(n^2), due to the space required for the 2D array dp.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subsequence GenerationO(2^n * n)O(2^n)Only for learning subsequence generation or very small strings
Dynamic Programming with Duplicate ControlO(n^2)O(n^2)General solution for counting distinct palindromic subsequences efficiently

Video Solution

LeetCode 730. Count Different Palindromic Subsequences Explanation and Solution • happygirlzt • 8,323 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Count Different Palindromic Subsequences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Palindromic Subsequences

Next

Longest Palindromic Subsequence