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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Count Different Palindromic Subsequences and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →