Count Different Palindromic Subsequences

Count Different Palindromic Subsequences

What is this problem about?

The Count Different Palindromic Subsequences coding problem asks you to find the number of unique non-empty palindromic subsequences in a string. Since the same subsequence can be formed in multiple ways, you only count distinct ones. You need to return the answer modulo 10^9 + 7.

Why is this asked in interviews?

This is a "Hard" Dynamic Programming interview pattern asked by Uber and LinkedIn. It tests your ability to handle 2D DP and de-duplication logic. It evaluates whether you can define a state that accounts for different characters at the boundaries of the string and how they contribute to new palindromes.

Algorithmic pattern used

The problem uses 2D Dynamic Programming.

1. Let dp[i][j] be the number of distinct palindromic subsequences in s[i..j].
2. If s[i] != s[j], dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1].
3. If s[i] == s[j], it gets more complex. Any palindrome in s[i+1..j-1] can be wrapped by s[i] and s[j] to form a new one. You also need to subtract duplicates based on how many times s[i] appears inside the inner substring.

Example explanation

s = "bccb"

1. Length 1: b, c, c, b. (Distinct: b, c).
2. Length 2: cc, bb, bc, cb (Wait, only palindromes). cc, bb.
3. Substrings:
   • c: 1
   • cc: 2 (c, cc)
   • bcc: 3 (b, c, cc)
   • bccb: The b...b wrap adds new palindromes. This requires careful calculation of the "inner" occurrences of the boundary character.

Common mistakes candidates make

• Not handling Duplicates: Simply using a standard "count all subsequences" formula, which doesn't account for the "distinct" requirement.
• Modulo Errors: Forgetting to handle negative results when subtracting dp[i+1][j-1]. Always use (a - b + MOD) % MOD.
• Complexity: An O(N^3) solution might be too slow; O(N^2) is the target using precomputed next/prev character indices.

Interview preparation tip

For "distinct subsequence" problems, the state usually needs to track where the first and last occurrences of a character are. Precalculating these positions can turn an O(N^3) DP into O(N^2).