#730

Count Different Palindromic Subsequences

candidate master · 1490 · lc hard +32 · verified · 47.6% accepted · 2,001 likes · top 32%

Description

Given a string s, count the number of distinct non-empty palindromic subsequences it contains. A subsequence is obtained by deleting zero or more characters; two subsequences are distinct if they differ at any position. Return the count modulo 10⁹ + 7.

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.

Code

1

2

3

class Solution:
    def countPalindromicSubsequences(self, s: str) -> int:

class Solution:
    def countPalindromicSubsequences(self, s: str) -> int: