2484. Count Different Palindromic Subsequences
Asked at Atlassian, Visa
Difficulty
Hard
Time
O(n^2)
Space
O(n^2)
Pattern
String
Companies
2
Problem
You are given a string s of digits. Count how many subsequences of s have length exactly 5 and are palindromes. A subsequence keeps the original order but you may delete any characters. A palindrome reads the same forwards and backwards. Two subsequences count separately if they come from different positions, even when the digits look the same. Return the count modulo 10^9 + 7.
Pick 5 positions, keep the order
Constraints
- ●
1 <= s.length <= 10^4 - ●
s consists of digits only
Examples
s = "103301"2s = "0000000"21s = "9999900000"2Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Atlassian | Hard | View all Atlassian questions → |
| Visa | Hard | View all Visa 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.
Interval DP on the ends
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
O(n^2) timefrom 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 runs in O(n^2) time and O(n^2) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Count Different Palindromic Subsequences?
Count Different Palindromic Subsequences is asked at Atlassian, Visa. 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).