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.
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:
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).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).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.
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.
| Approach | Complexity |
|---|---|
| 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. |
| Default Approach | — |
| 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 |
花花酱 LeetCode 730. Count Different Palindromic Subsequences - 刷题找工作 EP114 • Hua Hua • 10,137 views views
Watch 9 more video solutions →Practice Count Different Palindromic Subsequences with our built-in code editor and test cases.
Practice on FleetCode