#730

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Different Palindromic Subsequences

Count Different Palindromic Subsequences leverages dynamic programming to count non-empty palindromic subsequences in a string modulo 10^9 + 7.

string dynamic programming

Problem Statement

Given a string s, you are asked to return the number of different non-empty palindromic subsequences in s, modulo 10^9 + 7. A subsequence is formed by deleting zero or more characters, and the sequence is palindromic if it reads the same forwards and backwards.

For example, in the string 'bccb', the 6 different non-empty palindromic subsequences are 'b', 'c', 'bb', 'cc', 'bcb', and 'bccb'. Due to large possible outputs, the result should be modulo 10^9 + 7. The solution should efficiently handle strings with lengths up to 1000 characters.

Examples

Example 1

Input: s = "bccb"

Output: 6

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

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 Approach

State Transition Dynamic Programming

Use dynamic programming to calculate dp(i, j), which represents the number of distinct palindromic subsequences in the substring S[i:j+1]. The transition relies on analyzing the characters at the boundaries, S[i] and S[j], and the interactions with the substrings between them.

Modulo Operations for Large Outputs

Since the output can be very large, each operation in the dynamic programming process must return values modulo 10^9 + 7 to avoid overflow and to meet the problem's constraints.

Overlapping Subproblems and Memoization

Dynamic programming helps solve the problem by breaking it into overlapping subproblems. Memoization is used to store previously computed results, avoiding redundant calculations and ensuring efficient computation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the final approach but generally involves O(n^2) due to the nested loop over substring ranges. Space complexity also depends on the approach, but a 2D table to store dp values will require O(n^2) space.

What Interviewers Usually Probe

The candidate understands dynamic programming and is able to apply it to string problems.
The candidate can efficiently manage large outputs using modulo arithmetic.
The candidate is aware of overlapping subproblems and optimizes using memoization.

Common Pitfalls or Variants

Common pitfalls

Failing to handle overlapping subproblems efficiently, leading to unnecessary recalculations.
Forgetting to apply the modulo operation, causing overflow or incorrect results.
Overcomplicating the problem, missing simpler dynamic programming solutions with manageable time complexity.

Follow-up variants

Consider if the string has repeated characters and how that affects the number of unique subsequences.
What happens if the input string contains only one character?
Explore optimization techniques if the string length is increased significantly.

FAQ

How can I optimize the dynamic programming solution for the Count Different Palindromic Subsequences problem?

You can optimize by focusing on memoization and reducing redundant calculations, especially when dealing with overlapping subproblems.

What is the role of the modulo operation in solving this problem?

The modulo operation ensures that the result doesn't overflow and stays within the problem's constraints, specifically modulo 10^9 + 7.

How can I handle large input sizes in the Count Different Palindromic Subsequences problem?

Efficient use of dynamic programming, particularly with memoization, helps solve large input sizes within the time limits.

What does dp(i, j) represent in the context of this problem?

dp(i, j) represents the number of distinct palindromic subsequences in the substring S[i:j+1].

How does the problem's string length limit affect the solution?

The string length limit requires a solution that scales efficiently, typically O(n^2) time complexity, to handle the largest possible inputs.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:
        mod = 10**9 + 7
        n = len(s)
        dp = [[[0] * 4 for _ in range(n)] for _ in range(n)]
        for i, c in enumerate(s):
            dp[i][i][ord(c) - ord('a')] = 1
        for l in range(2, n + 1):
            for i in range(n - l + 1):
                j = i + l - 1
                for c in 'abcd':
                    k = ord(c) - ord('a')
                    if s[i] == s[j] == c:
                        dp[i][j][k] = 2 + sum(dp[i + 1][j - 1])
                    elif s[i] == c:
                        dp[i][j][k] = dp[i][j - 1][k]
                    elif s[j] == c:
                        dp[i][j][k] = dp[i + 1][j][k]
                    else:
                        dp[i][j][k] = dp[i + 1][j - 1][k]
        return sum(dp[0][-1]) % mod

Continue Practicing

#712 minimum ascii delete sum for two strings #691 stickers to spell word #678 valid parenthesis string