325. Longest Palindromic Subsequence

Given a string, find the length of its longest palindromic subsequence - the longest sequence of characters (not necessarily contiguous) that reads the same forwards and backwards.

Input: A single line contains the string s. Output: Print a single integer - the length of the longest palindromic subsequence of s.

1 <= |s| <= 2000

Filling the table by INCREASING SUBSTRING LENGTH (not simply by increasing i or j alone) is essential - dp[i][j] depends on strictly SHORTER ranges, so the fill order must respect this dependency to ensure every needed value is already computed.

Find the length of the longest subsequence of a string that reads the same forwards and backwards. Brute force: Try every possible subsequence (2^n of them) and check which are palindromes, taking the longest - this is exponential, impractical for |s| up to 2000. Optimised: The DP table builds up from SHORTER substrings to LONGER ones, reusing already-computed smaller answers - matching outer characters extends a palindrome found in the middle, while non-matching characters fall back to the best of two slightly smaller sub-problems, avoiding any re-exploration of overlapping ranges.

Define a recursive function on the substring bounds (i, j): if i > j return 0, if i == j return 1, if s[i] == s[j] return 2 plus the recursive result for (i+1, j-1), otherwise return the maximum of the recursive results for (i+1, j) and (i, j-1). Called without any caching, this recomputes the same (i, j) subproblems repeatedly, giving exponential blowup because the same substring bounds are revisited along many different recursive paths. Time: O(2^n) Space: O(n) recursion depth

Use the same recursive relation as the brute approach, but store the result for each (i, j) pair the first time it's computed in a 2D memo table, and return the cached value immediately on any later call with the same bounds. Since there are only O(n^2) distinct (i, j) pairs and each is computed once in O(1) work given its subresults, the exponential recursion collapses to polynomial time. Time: O(n^2) Space: O(n^2)

Observe that the longest palindromic subsequence of s equals the longest common subsequence of s and its reverse, and that computing it via increasing substring length (bottom-up dynamic programming, filling dp[i][j] for smaller lengths first) only ever needs the row for length-1-shorter substrings to compute the current row. Iterate substring lengths from 1 up to n, keeping only the previous length's values in a 1D array and updating in place, using the same match/no-match recurrence as before. This keeps the same O(n^2) time as the full 2D table but reduces the memory footprint to linear. Time: O(n^2) Space: O(n)

1. dp[i][j] = length of the longest palindromic subsequence within substring s[i..j]. 2. Every single character is trivially a palindrome of length 1: dp[i][i]=1. 3. If s[i]==s[j], dp[i][j]=dp[i+1][j-1]+2 (or just 2 when j==i+1); otherwise dp[i][j]=max(dp[i+1][j], dp[i][j-1]) - fill by increasing substring length, since longer ranges depend on shorter ones.

Time: O(n²) - filling the DP table, one cell per substring range. Space: O(n²) for the full table (reducible to O(n) with careful diagonal-order processing, since each cell only depends on cells with shorter ranges).

Test a single-character string (answer 1), a string that is already a palindrome (answer equals |s|), and |s| = 2000 (upper bound) for the O(n^2) DP's performance.

Be ready to connect this directly to LCS: the longest palindromic subsequence of a string equals the LCS of that string and its own REVERSE - an elegant alternative technique worth mentioning alongside the direct interval DP.