Skip to main content

730. Count Different Palindromic Subsequences

hard

Count DISTINCT palindromic subsequences of s. Interval DP with a careful case analysis on whether s[i] == s[j], plus tracking the nearest matching positions inside the interval to avoid double-counting.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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 10^9 + 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.

Constraints

  • 1 <= s.length <= 1000
  • s[i] is either 'a', 'b', 'c', or 'd'.

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Interval DP. dp[i][j] = number of distinct palindromic subsequences in s[i..j].

Hint 2

If s[i] != s[j]: dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] (inclusion-exclusion).

Hint 3

If s[i] == s[j]: find the nearest s[i] from the left (call it l) and from the right (call it r) in [i+1, j-1]. Three subcases by whether l < r, l == r, or no match in between, each with its own count formula.

Hint 4

Apply mod 10^9 + 7. Fill by increasing interval length.

Solution approach

Reveal approach

Interval DP with three subcases when the endpoints match. dp[i][j] is the number of distinct non-empty palindromic subsequences inside s[i..j]. Base case: dp[i][i] = 1 (a single char). If s[i] != s[j], dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1] (inclusion-exclusion on which endpoint to drop). If s[i] == s[j], scan for the leftmost l > i with s[l] == s[i] and the rightmost r < j with s[r] == s[i]. Case A: no such l within (i, j): dp[i][j] = 2 * dp[i+1][j-1] + 2 (each inner palindromic subseq gets a new wrap, plus the two new ones s[i] and s[i]s[i]). Case B: l == r (exactly one inner match): dp[i][j] = 2 * dp[i+1][j-1] + 1 (the single-char inner duplicate makes the empty-inner case redundant). Case C: l < r: dp[i][j] = 2 * dp[i+1][j-1] - dp[l+1][r-1] (subtract the doubly-counted palindromes wrapped between the inner matches). All arithmetic mod 10^9 + 7. Fill by increasing length.

Complexity

Time
O(n^2)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • interval-dp
  • string-dp
  • inclusion-exclusion

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →