Count Palindromic Subsequences
Description
Given a string s of length n, count the total number of palindromic subsequences present in the string. The subsequences need not be distinct — two subsequences formed by selecting characters at different positions are counted separately even if they produce the same string.
A subsequence is a sequence derived from the string by deleting zero or more characters without changing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde".
A palindrome is a string that reads the same forward and backward. For example, "aba", "aa", and "a" are all palindromes.
Note that every single character is itself a palindromic subsequence of length 1.
Examples
Example 1
Input: s = "abcd"
Output: 4
Explanation: Every character on its own is a palindrome: "a", "b", "c", "d". No multi-character subsequence forms a palindrome because all characters are distinct — for instance, "ab" reversed is "ba" which differs from "ab". Therefore the count is 4.
Example 2
Input: s = "aab"
Output: 4
Explanation: The palindromic subsequences are:
- "a" (using index 0)
- "a" (using index 1)
- "b" (using index 2)
- "aa" (using indices 0 and 1)
The two single-character "a" subsequences are counted separately because they come from different positions. The subsequence "ab" (indices 0,2 or 1,2) is not a palindrome, and "aab" (all three) is not a palindrome. Total: 4.
Example 3
Input: s = "aba"
Output: 5
Explanation: The palindromic subsequences are:
- "a" (index 0)
- "b" (index 1)
- "a" (index 2)
- "aa" (indices 0 and 2) — the two 'a's at the ends form a palindrome
- "aba" (indices 0, 1, and 2) — the full string is itself a palindrome
Note that "ab" and "ba" are not palindromes. Total: 5.
Constraints
- 1 ≤ |s| ≤ 1000
- s consists of lowercase English letters
Editorial
Brute Force
Intuition
The simplest way to solve this is to enumerate every possible subsequence of the string and check whether each one is a palindrome.
Think of it like a buffet with n dishes. For each dish you make a binary choice: take it or leave it. That gives you 2^n possible plates (including the empty plate, which we skip). For each plate, you check if the arrangement reads the same forward and backward.
We can generate all subsequences using recursion. At each character in the string, we either include it in the current subsequence or skip it. When we reach the end of the string, we check if the accumulated subsequence is a palindrome and count it if so.
Step-by-Step Explanation
Let's trace through with s = "aab":
We generate all 2^3 - 1 = 7 non-empty subsequences and test each:
Step 1: Select index 0 only → subsequence "a". Is "a" a palindrome? Yes (single character). Count = 1.
Step 2: Select indices 0, 1 → subsequence "aa". Is "aa" a palindrome? Check: first char 'a' == last char 'a'. Yes! Count = 2.
Step 3: Select indices 0, 1, 2 → subsequence "aab". Is "aab" a palindrome? Check: first char 'a' ≠ last char 'b'. No. Count stays 2.
Step 4: Select indices 0, 2 → subsequence "ab". Is "ab" a palindrome? Check: 'a' ≠ 'b'. No. Count stays 2.
Step 5: Select index 1 only → subsequence "a". Is "a" a palindrome? Yes. Count = 3.
Step 6: Select indices 1, 2 → subsequence "ab". Is "ab" a palindrome? No. Count stays 3.
Step 7: Select index 2 only → subsequence "b". Is "b" a palindrome? Yes. Count = 4.
Step 8: All 7 subsequences checked. Return 4.
Brute Force — Generating and Testing All Subsequences — Watch how each non-empty subsequence is formed by selecting characters at specific indices, then tested for the palindrome property.
Algorithm
- Define a recursive function
generate(s, idx, current):- Base case: If
idx == n, check ifcurrentis non-empty and a palindrome. Return 1 if yes, 0 otherwise. - Include: Recurse with
current + s[idx]andidx + 1 - Exclude: Recurse with
currentunchanged andidx + 1 - Return the sum of both recursive calls
- Base case: If
- Call
generate(s, 0, "")and return the result
Code
#include <string>
using namespace std;
class Solution {
bool isPalindrome(const string& sub) {
int left = 0, right = sub.size() - 1;
while (left < right) {
if (sub[left] != sub[right]) return false;
left++;
right--;
}
return true;
}
int generate(const string& s, int idx, string current) {
if (idx == (int)s.size()) {
if (!current.empty() && isPalindrome(current))
return 1;
return 0;
}
int include = generate(s, idx + 1, current + s[idx]);
int exclude = generate(s, idx + 1, current);
return include + exclude;
}
public:
int countPS(string s) {
return generate(s, 0, "");
}
};class Solution:
def countPS(self, s: str) -> int:
def is_palindrome(sub: str) -> bool:
return sub == sub[::-1]
def generate(idx: int, current: str) -> int:
if idx == len(s):
if current and is_palindrome(current):
return 1
return 0
include = generate(idx + 1, current + s[idx])
exclude = generate(idx + 1, current)
return include + exclude
return generate(0, "")class Solution {
private boolean isPalindrome(String sub) {
int left = 0, right = sub.length() - 1;
while (left < right) {
if (sub.charAt(left) != sub.charAt(right)) return false;
left++;
right--;
}
return true;
}
private int generate(String s, int idx, String current) {
if (idx == s.length()) {
if (!current.isEmpty() && isPalindrome(current))
return 1;
return 0;
}
int include = generate(s, idx + 1, current + s.charAt(idx));
int exclude = generate(s, idx + 1, current);
return include + exclude;
}
public int countPS(String s) {
return generate(s, 0, "");
}
}Complexity Analysis
Time Complexity: O(n × 2^n)
At each of the n characters, we make two choices (include or exclude), producing 2^n total subsequences. For each subsequence, we check if it is a palindrome in O(n) time by comparing characters from both ends. Total: O(n × 2^n).
Space Complexity: O(n)
The recursion depth is at most n (one level per character). At each level we also build a substring of at most length n. Therefore, space used by the call stack and the accumulated string is O(n).
Why This Approach Is Not Efficient
With n up to 1000, the brute force generates 2^1000 subsequences — a number with over 300 digits. Even 2^30 ≈ 10^9 is borderline, and n = 1000 is astronomically beyond any feasible computation.
The root cause of the inefficiency is that we treat every subsequence independently. We generate "ab", check it, discard it, then generate "aab", check it, discard it — never reusing any work. But many of these subsequences share structure: the palindromic subsequences in "aab" include all palindromic subsequences in "ab" plus all in "aa" minus the overlap. This is the hallmark of overlapping subproblems.
The key insight is to reframe the problem. Instead of asking "is each subsequence a palindrome?", ask: "how many palindromic subsequences exist in the substring from index i to index j?" This question has only O(n²) unique answers (one for each pair i, j), and each answer can be built from smaller substrings. This is the foundation for a dynamic programming solution that runs in O(n²) instead of O(n × 2^n).
Better Approach - Recursion with Memoization
Intuition
Instead of generating every subsequence, we define a function count(i, j) that returns the number of palindromic subsequences in the substring s[i..j]. We can break this down by looking at the characters at the two ends of the substring.
Case 1: s[i] == s[j] (boundary characters match)
When the first and last characters are the same, three sets of palindromes exist:
- Palindromes that live entirely within
s[i+1..j](those not using position i) - Palindromes that live entirely within
s[i..j-1](those not using position j) - A brand-new palindrome formed by pairing s[i] with s[j] — the pair "s[i]s[j]" itself
Sets 1 and 2 overlap: both contain all palindromes in s[i+1..j-1]. By inclusion-exclusion, the union is count(i+1, j) + count(i, j-1) - count(i+1, j-1). Adding the new palindrome formed by the matching pair gives:
count(i, j) = count(i+1, j) + count(i, j-1) - count(i+1, j-1) + count(i+1, j-1) + 1
The -count(i+1, j-1) and +count(i+1, j-1) cancel out, simplifying to:
count(i, j) = count(i+1, j) + count(i, j-1) + 1
The +1 accounts for the palindrome formed by just the two matching boundary characters.
Case 2: s[i] ≠ s[j] (boundary characters differ)
The boundary characters can never be the outer pair of a palindrome together. By inclusion-exclusion:
count(i, j) = count(i+1, j) + count(i, j-1) - count(i+1, j-1)
We subtract count(i+1, j-1) because it is counted in both count(i+1, j) and count(i, j-1).
Base cases:
i > j: empty substring → 0 palindromesi == j: single character → exactly 1 palindrome
Since many pairs (i, j) are computed repeatedly during recursion, we store each result in a memo table the first time we compute it, and return the cached value on future calls. This eliminates redundant work and reduces the total number of distinct computations to O(n²).
Step-by-Step Explanation
Let's trace the recursion for s = "aab" (indices 0, 1, 2):
Step 1: Call count(0, 2). s[0]='a' ≠ s[2]='b' → need count(1,2), count(0,1), and count(1,1).
Step 2: Recurse into count(1, 2). s[1]='a' ≠ s[2]='b' → need count(2,2), count(1,1), count(2,1).
Step 3: count(2, 2) is a base case: single character 'b' → returns 1.
Step 4: count(1, 1) is a base case: single character 'a' → returns 1. Store in memo[(1,1)] = 1.
Step 5: count(2, 1): since i > j (2 > 1), this is an empty substring → returns 0.
Step 6: Resolve count(1, 2) = count(2,2) + count(1,1) - count(2,1) = 1 + 1 - 0 = 2. Store in memo.
Step 7: Recurse into count(0, 1). s[0]='a' == s[1]='a' → matching characters! Need count(1,1) and count(0,0).
Step 8: count(1, 1): Found in memo! Returns 1 immediately. No recomputation needed.
Step 9: count(0, 0) is a base case: single character 'a' → returns 1.
Step 10: Resolve count(0, 1) = count(1,1) + count(0,0) + 1 = 1 + 1 + 1 = 3. The +1 counts the new palindrome "aa" formed by the matching boundary characters.
Step 11: count(1, 1) for the subtraction in count(0,2): Found in memo again! Returns 1.
Step 12: Resolve count(0, 2) = count(1,2) + count(0,1) - count(1,1) = 2 + 3 - 1 = 4. Return 4.
Memoized Recursion — Avoiding Redundant Subproblems — Watch the recursion tree unfold and see how memoization prevents recomputing count(1,1) multiple times, turning exponential branching into polynomial work.
Algorithm
- Create an n × n memoization table initialized to -1
- Define
solve(i, j):- If
i > j, return 0 (empty substring) - If
i == j, return 1 (single character) - If
memo[i][j] != -1, return cached value - If
s[i] == s[j]:memo[i][j] = solve(i+1, j) + solve(i, j-1) + 1 - If
s[i] != s[j]:memo[i][j] = solve(i+1, j) + solve(i, j-1) - solve(i+1, j-1) - Return
memo[i][j]
- If
- Call
solve(0, n-1)and return the result
Code
#include <string>
#include <vector>
using namespace std;
class Solution {
int solve(const string& s, int i, int j,
vector<vector<int>>& memo) {
if (i > j) return 0;
if (i == j) return 1;
if (memo[i][j] != -1) return memo[i][j];
if (s[i] == s[j])
memo[i][j] = solve(s, i + 1, j, memo)
+ solve(s, i, j - 1, memo) + 1;
else
memo[i][j] = solve(s, i + 1, j, memo)
+ solve(s, i, j - 1, memo)
- solve(s, i + 1, j - 1, memo);
return memo[i][j];
}
public:
int countPS(string s) {
int n = s.size();
vector<vector<int>> memo(n, vector<int>(n, -1));
return solve(s, 0, n - 1, memo);
}
};class Solution:
def countPS(self, s: str) -> int:
n = len(s)
memo = [[-1] * n for _ in range(n)]
def solve(i: int, j: int) -> int:
if i > j:
return 0
if i == j:
return 1
if memo[i][j] != -1:
return memo[i][j]
if s[i] == s[j]:
memo[i][j] = solve(i + 1, j) + solve(i, j - 1) + 1
else:
memo[i][j] = (solve(i + 1, j) + solve(i, j - 1)
- solve(i + 1, j - 1))
return memo[i][j]
return solve(0, n - 1)import java.util.Arrays;
class Solution {
private int[][] memo;
private int solve(String s, int i, int j) {
if (i > j) return 0;
if (i == j) return 1;
if (memo[i][j] != -1) return memo[i][j];
if (s.charAt(i) == s.charAt(j))
memo[i][j] = solve(s, i + 1, j)
+ solve(s, i, j - 1) + 1;
else
memo[i][j] = solve(s, i + 1, j)
+ solve(s, i, j - 1)
- solve(s, i + 1, j - 1);
return memo[i][j];
}
public int countPS(String s) {
int n = s.length();
memo = new int[n][n];
for (int[] row : memo) Arrays.fill(row, -1);
return solve(s, 0, n - 1);
}
}Complexity Analysis
Time Complexity: O(n²)
There are O(n²) unique subproblems — one for each pair (i, j) where 0 ≤ i ≤ j < n. Each subproblem performs O(1) work (a constant number of additions and a comparison). Due to memoization, each subproblem is computed at most once. Total: O(n²).
Space Complexity: O(n²)
The memo table stores results for up to n × n pairs. Additionally, the recursion stack can grow to depth O(n) in the worst case (when all calls go to smaller substrings before returning). The dominant term is the O(n²) memo table.
Why This Approach Is Not Efficient
The memoized recursion achieves O(n²) time, which is a massive improvement over the exponential brute force. However, it has practical drawbacks:
-
Recursion overhead: Each of the O(n²) subproblems incurs function call overhead — pushing/popping stack frames, saving/restoring local variables. This constant factor is measurably slower than iterative code.
-
Stack depth risk: The recursion can reach depth O(n). For n = 1000, this means up to 1000 nested calls. While most systems handle this, it is unnecessarily close to default stack limits and fragile under tighter environments.
-
Unpredictable order: Top-down memoization computes subproblems in the order they happen to be needed, which can lead to poor cache locality — the processor's cache works best when memory is accessed sequentially, not scattered across the memo table.
All three issues vanish if we fill the same DP table bottom-up using loops instead of recursion. The recurrence is identical, but the iterative approach eliminates function call overhead, avoids stack depth concerns entirely, and fills cells in a predictable sequential order that is cache-friendly.
Optimal Approach - Bottom-Up Dynamic Programming
Intuition
We use the exact same recurrence as the memoized solution but flip the execution order. Instead of starting from the full string and recursing into smaller substrings, we start from the smallest substrings and build upward.
Define dp[i][j] = the number of palindromic subsequences in the substring s[i..j].
Base cases:
dp[i][i] = 1for all i (every single character is a palindromic subsequence)dp[i][j] = 0when i > j (empty substring)
Recurrence (fill order: increasing substring length):
- If
s[i] == s[j]:dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1 - If
s[i] != s[j]:dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
The answer is dp[0][n-1].
Imagine filling an upper-triangular matrix. The diagonal (length-1 substrings) is filled first. Then we fill cells for length-2 substrings, then length-3, and so on. At each cell, the values we need (from shorter substrings) are already computed and sitting in the table. No recursion, no stack, no memoization lookup — just direct table reads.
![DP table dependency diagram showing how dp[i][j] is computed from dp[i+1][j], dp[i][j-1], and dp[i+1][j-1]](https://pub-a1b3030acfb94e84ba8a89fb182c53bc.r2.dev/public/83d5c8e7-feb5-4ad8-a98d-a2c8000dda45/dp_dependency_diagram_v1.webp)
Step-by-Step Explanation
Let's trace the DP table for s = "aab" (n = 3, indices 0, 1, 2).
The table is 3×3. Only the upper triangle (i ≤ j) is meaningful.
Step 1: Initialize the diagonal — every single character is 1 palindromic subsequence:
- dp[0][0] = 1 (substring "a")
- dp[1][1] = 1 (substring "a")
- dp[2][2] = 1 (substring "b")
Step 2: Fill length-2 substrings. Start with dp[0][1] (substring "aa").
- s[0]='a' == s[1]='a' → matching! Use the match formula.
Step 3: Compute dp[0][1] = dp[1][1] + dp[0][0] + 1 = 1 + 1 + 1 = 3.
- The 3 palindromic subsequences in "aa" are: "a" (idx 0), "a" (idx 1), "aa".
- The +1 counted "aa" — the palindrome formed by the two matching boundary characters.
Step 4: Fill dp[1][2] (substring "ab").
- s[1]='a' ≠ s[2]='b' → non-matching. Use the non-match formula.
Step 5: Compute dp[1][2] = dp[2][2] + dp[1][1] - dp[2][1] = 1 + 1 - 0 = 2.
- dp[2][1] = 0 because i > j (empty substring).
- The 2 palindromic subsequences in "ab" are: "a" and "b".
Step 6: Fill length-3 substring. dp[0][2] (full string "aab").
- s[0]='a' ≠ s[2]='b' → non-matching.
Step 7: Compute dp[0][2] = dp[1][2] + dp[0][1] - dp[1][1] = 2 + 3 - 1 = 4.
- Inclusion-exclusion: palindromes in "ab" (2) + palindromes in "aa" (3) − palindromes in "a" at index 1 (1, counted in both).
Step 8: Result: dp[0][n-1] = dp[0][2] = 4.
Bottom-Up DP Table — Filling by Substring Length — Watch the DP table fill from the diagonal outward, building solutions for longer substrings from already-computed shorter ones.
Algorithm
- Create an n × n DP table initialized to 0
- Base case: Set
dp[i][i] = 1for all i (single characters) - Fill by increasing length from 2 to n:
- For each starting index
ifrom 0 ton - length:- Compute
j = i + length - 1 - If
s[i] == s[j]:dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1 - If
s[i] != s[j]:dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1]
- Compute
- For each starting index
- Return
dp[0][n-1]
Code
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
int countPS(string s) {
int n = s.size();
vector<vector<int>> dp(n, vector<int>(n, 0));
// Base case: every single character is a palindrome
for (int i = 0; i < n; i++)
dp[i][i] = 1;
// Fill for increasing substring lengths
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s[i] == s[j])
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] + 1;
else
dp[i][j] = dp[i + 1][j] + dp[i][j - 1]
- dp[i + 1][j - 1];
}
}
return dp[0][n - 1];
}
};class Solution:
def countPS(self, s: str) -> int:
n = len(s)
dp = [[0] * n for _ in range(n)]
# Base case: single characters
for i in range(n):
dp[i][i] = 1
# Fill for increasing substring lengths
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j]:
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] + 1
else:
dp[i][j] = (dp[i + 1][j] + dp[i][j - 1]
- dp[i + 1][j - 1])
return dp[0][n - 1]class Solution {
public int countPS(String s) {
int n = s.length();
int[][] dp = new int[n][n];
// Base case: single characters
for (int i = 0; i < n; i++)
dp[i][i] = 1;
// Fill for increasing substring lengths
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
if (s.charAt(i) == s.charAt(j))
dp[i][j] = dp[i + 1][j] + dp[i][j - 1] + 1;
else
dp[i][j] = dp[i + 1][j] + dp[i][j - 1]
- dp[i + 1][j - 1];
}
}
return dp[0][n - 1];
}
}Complexity Analysis
Time Complexity: O(n²)
The outer loop iterates over substring lengths from 2 to n (O(n) iterations). For each length, the inner loop iterates over starting positions (up to O(n) positions). Inside, each cell is computed in O(1) time using the recurrence. Total: O(n) × O(n) × O(1) = O(n²).
For n = 1000, this means roughly 500,000 cell computations — easily within time limits.
Space Complexity: O(n²)
The DP table is an n × n 2D array. For n = 1000, this is 10^6 integers — about 4 MB with 32-bit integers, well within memory limits.
Compared to the memoized approach, the bottom-up approach uses the same asymptotic space for the table but eliminates the O(n) recursion stack, making it strictly better in practice.