65. Count Palindromic Subsequences in a String

Given a string s, count the number of subsequences of s (choices of index subsets, not necessarily distinct as strings) that form a palindrome. Every single character counts as a palindromic subsequence of length 1. Print the total count.

Input: The input is a single line containing the string s. Output: Print a single integer - the total count of palindromic subsequences in s.

1 <= |s| <= 1000

Every single character by itself always counts as a palindromic subsequence of length 1 - a useful sanity-check baseline (the answer for any non-empty string is always at least equal to its length).

Count how many different ways you can pick a subset of a string's characters (keeping their order) that read the same forwards and backwards. Brute force: Generate every possible subsequence directly (2^n of them) and check each one for being a palindrome - this is exponential, impractical beyond very short strings. Optimised: The DP table captures the reusable insight that counting palindromic subsequences within a substring only depends on the counts within slightly smaller substrings - the careful 'add when matching, subtract to avoid double-count when not' recurrence correctly accounts for overlapping counts between the two shrink directions, turning exponential enumeration into a table with O(n²) cells.

Define count(i,j) as the number of palindromic subsequences within s[i..j]. If s[i] equals s[j], every palindromic subsequence of s[i+1..j] and of s[i..j-1] is counted, but the ones already inside s[i+1..j-1] get counted twice, and s[i]/s[j] can also each be added around those or used alone, giving count(i,j) = count(i+1,j) + count(i,j-1) + 1. If s[i] differs from s[j], count(i,j) = count(i+1,j) + count(i,j-1) - count(i+1,j-1), subtracting off the double-counted middle interval. Memoizing on the (i,j) pair means each interval is computed only once instead of recomputed exponentially often. Time: O(n^2) Space: O(n^2)

Enumerate every one of the 2^n possible subsequences of s by deciding, independently for each index, whether to include it or not, form the resulting subsequence, and check whether it reads the same forwards and backwards. This directly matches the problem's definition of counting index subsets that form a palindrome, but it is exponential and becomes infeasible once the string has more than about 20-25 characters. Time: O(2^n * n) Space: O(n)

Compute the exact same recurrence iteratively, filling the DP table by increasing substring length so that count(i+1,j), count(i,j-1), and count(i+1,j-1) are always already known by the time count(i,j) is computed. This removes recursion-call overhead and the risk of deep recursion for strings up to length 1000, and lets the table be filled with simple nested loops in a guaranteed-safe order. Time: O(n^2) Space: O(n^2)

1. Build a 2D DP table where dp[i][j] means 'the count of palindromic subsequences within the substring from index i to j'. 2. If the characters at the two ends (s[i] and s[j]) match, combine the counts from shrinking either end, PLUS 1 for the new palindrome formed by wrapping this matching pair around everything in between. 3. If they don't match, combine the counts from shrinking either end, but SUBTRACT the middle region's count once to avoid counting it twice (since it was included in both shrink directions).

Time: O(n²) - filling the DP table, one cell per pair of substring boundaries. Space: O(n²), for the full DP table.

A single-character string (count 1); a string of all identical characters, which stresses the inclusion-exclusion in the DP recurrence; s up to length 1000 for performance.

Be ready to carefully explain the subtraction step for the non-matching case - it's the single most error-prone part of this recurrence, and interviewers often specifically probe whether you understand WHY the subtraction is needed (to avoid double-counting the middle region).