Count Different Palindromic Subsequences
Asked at Atlassian
Problem
Given a string s of lowercase letters a-d, return the number of distinct palindromic subsequences in s modulo 10^9+7. A subsequence is palindromic if it reads the same forwards and backwards.
Asked At
| Company | Difficulty | |
|---|---|---|
| Atlassian | Hard | View all Atlassian questions → |
How to Think About It
Brute force: generate all 2^n subsequences, check each for palindrome. Count distinct ones. Time O(2^n * n) which is infeasible.
Key insight: interval DP. Let f(i,j) = number of distinct palindromic subsequences in s[i..j]. Recurse on smaller intervals and combine results.
Recurrence when s[i] == s[j]: find the first occurrence of s[i] after i (call it k) and the last occurrence before j (call it p). If no inner occurrence: 2f(i+1,j-1)+2. If one inner: 2f(i+1,j-1)+1. If two+: 2*f(i+1,j-1)-f(k+1,p-1).
Recurrence when s[i] != s[j]: f(i,j) = f(i+1,j) + f(i,j-1) - f(i+1,j-1). Inclusion-exclusion of the two sub-intervals.
Precompute next and prev occurrence arrays: nxt[i][c] = next index >= i with character c. prv[i][c] = previous index <= i with character c. This makes inner-occurrence lookup O(1).
Base cases: f(i,j) = 0 when i > j (empty). f(i,j) = 1 when i == j (single character). All 4 characters a-d appear in s.
Optimal Approach
Step 1: Precompute nxt[i][c] and prv[i][c] for each position i and character c in {a,b,c,d}.
Step 2: Define dp(i,j) with memoization:
- Base: i > j -> 0. i == j -> 1.
- If s[i] == s[j]:
k = nxt[i+1][s[i]], p = prv[j-1][s[i]]
if k > j: 2dp(i+1,j-1) + 2
elif k == p: 2dp(i+1,j-1) + 1
else: 2*dp(i+1,j-1) - dp(k+1,p-1) - Else: dp(i+1,j) + dp(i,j-1) - dp(i+1,j-1)
All modulo 10^9+7.
Step 3: Return dp(0, n-1).
Walkthrough for s="aba":
- dp(0,2): s[0]=a, s[2]=a. k=nxt[1][a]=2, p=prv[1][a]=0. k(2)>j(2)? No. k==p? 2!=0, no. k<p? 0<2 yes -> two+ inner? No, k(2)>p(0). Actually k=2, p=0 -> k>j(2)? k==j, so k is at j boundary. This means no inner occurrence between i+1 and j-1. -> 2dp(1,1)+2 = 21+2=4.
- Distinct palindromic subsequences of "aba": "a","b","aa","aba" -> 4. Correct.
Time: O(n^2) states, O(1) per state. Space: O(n^2) for memoization.
What Trips People Up in Real Interviews
Forgetting the subtraction term when s[i]==s[j] and there are two+ inner occurrences. Without subtracting f(k+1,p-1), you double-count palindromes that are already counted twice.
Using the wrong base case. Empty string (i>j) returns 0, single character (i==j) returns 1. Do not return 1 for empty.
Not handling the modulo correctly. After subtraction, the result can be negative. Add MOD before taking modulo: (x - y + MOD) % MOD.
Confusing distinct palindromic SUBSEQUENCES with SUBSTRINGS. Subsequences skip characters; substrings are contiguous. The DP works on substrings but counts subsequences.
Off-by-one in next/prev arrays. nxt[i][c] should search from i+1 to n-1 (exclusive of i). prv[j][c] should search from 0 to j-1 (exclusive of j).
Solution Code
from functools import lru_cache
class Solution:
def countPalindromicSubsequences(self, s):
n = len(s)
MOD = 10**9 + 7
nxt = [[n]*26 for _ in range(n+1)]
prv = [[-1]*26 for _ in range(n)]
for i in range(n):
for c in range(26):
prv[i][c] = prv[i-1][c] if i else -1
prv[i][ord(s[i])-97] = i
for i in range(n-1, -1, -1):
for c in range(26):
nxt[i][c] = nxt[i+1][c]
nxt[i][ord(s[i])-97] = i
@lru_cache(None)
def dp(i, j):
if i > j: return 0
if i == j: return 1
ci = ord(s[i]) - 97
if s[i] == s[j]:
k = nxt[i+1][ci]
p = prv[j-1][ci]
if k > j:
return (2 * dp(i+1, j-1) + 2) % MOD
if k == p:
return (2 * dp(i+1, j-1) + 1) % MOD
return (2 * dp(i+1, j-1) - dp(k+1, p-1)) % MOD
else:
return (dp(i+1, j) + dp(i, j-1) - dp(i+1, j-1)) % MOD
return dp(0, n-1) % MODFrequently Asked Questions
What is the Count Different Palindromic Subsequences problem?
Given a string s of lowercase letters a-d, return the number of distinct palindromic subsequences in s modulo 10^9+7. A subsequence is palindromic if it reads the same forwards and backwards.
How do you solve Count Different Palindromic Subsequences?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Count Different Palindromic Subsequences?
Count Different Palindromic Subsequences is asked at Atlassian. It is a hard difficulty problem.
What are common mistakes on Count Different Palindromic Subsequences?
- Forgetting the subtraction term when s[i]==s[j] and there are two+ inner occurrences. Without subtracting f(k+1,p-1), you double-count palindromes that are already counted twice.
- Using the wrong base case. Empty string (i>j) returns 0, single character (i==j) returns 1. Do not return 1 for empty.
- Not handling the modulo correctly. After subtraction, the result can be negative. Add MOD before taking modulo: `(x - y + MOD) % MOD`.
- Confusing distinct palindromic SUBSEQUENCES with SUBSTRINGS. Subsequences skip characters; substrings are contiguous. The DP works on substrings but counts subsequences.
- Off-by-one in next/prev arrays. nxt[i][c] should search from i+1 to n-1 (exclusive of i). prv[j][c] should search from 0 to j-1 (exclusive of j).