Watch 10 video solutions for Count Different Palindromic Subsequences, a hard level problem involving String, Dynamic Programming. This walkthrough by Hua Hua has 10,137 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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'.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 | 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 |