{x}
blog image

Count Different Palindromic Subsequences

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'.

Solution Explanation:

This problem asks to find the number of different non-empty palindromic subsequences in a given string. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. A palindromic sequence reads the same forwards and backward.

The most efficient approach is using dynamic programming. We'll build a 3D DP table where:

  • dp[i][j][k] represents the number of distinct palindromic subsequences of length at least 1 within the substring s[i...j] that end with character k ('a'=0, 'b'=1, 'c'=2, 'd'=3).

The base cases are when i == j: dp[i][i][k] is 1 if s[i] is character k, otherwise 0.

The recursive relation is built as follows:

  1. s[i] == s[j] == c: If the characters at both ends of the substring are the same and equal to character c, then we have several possibilities:

    • All palindromic subsequences within s[i+1...j-1].
    • Palindromic subsequences ending with c (s[i], s[j]). This adds 2 to the count (unless the substring s[i+1...j-1] already contains c, in which case it would be already included).

  2. s[i] == c or s[j] == c: If only one of the ends matches character c, then the count is simply inherited from the smaller substring that ends in c.

  3. s[i] != c and s[j] != c: If neither end matches character c, then the count is inherited from the inner substring s[i+1...j-1].

The final answer is the sum of dp[0][n-1][k] for all k (0 to 3), representing the total number of distinct palindromic subsequences in the entire string.

Time and Space Complexity Analysis:

  • Time Complexity: O(n^2 * 4), where n is the length of the string. We iterate through all possible substrings (O(n^2)) and for each substring, consider each of the 4 possible characters ('a', 'b', 'c', 'd').

  • Space Complexity: O(n^2 * 4) to store the DP table.

Code in Different Languages:

The code provided in the original response is well-structured and efficient. It directly implements the dynamic programming solution described above. Note that the modulo operator (%) is used to prevent integer overflow, as the number of palindromic subsequences can become very large. Each language version shows a slightly different approach for handling this optimization, but the core logic is identical.