Count Palindromic Subsequences

Medium

Interval DP over start and end

Problem

Count the number of palindromic subsequences in a string (or distinct ones, per definition).

In simple words

Count via intervals: matching ends add the inner count plus one new pair; otherwise inclusion-exclusion.

The idea

Let dp[i][j] count palindromic subsequences in the substring i..j. When the end characters match they pair up with everything inside, otherwise you combine the two smaller intervals and subtract the doubly-counted overlap by inclusion-exclusion.

The trick

Matching ends: dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1.
Mismatched ends: dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1].
Fill by increasing interval length; O(n²) time and space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

←→stepspaceplay

1/2

Optimal

timeO(n^2)spaceO(n^2)

1dp[i][j] = palindromic subsequences in s[i..j]2if s[i]==s[j]: dp = dp[i+1][j]+dp[i][j-1]+1 else subtract overlap

Input

array: [0]

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: s = "aab"
Output:: 4
Explanation:: Palindromic subsequences: a, a, b, aa → 4.

Example 2

Input:: s = "aba"
Output:: 5
Explanation:: a, b, a, aa, aba → 5.

Example 3

Input:: s = "a"
Output:: 1
Explanation:: Just 'a' → 1.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.