381. What is the difference between the longest palindromic subsequence and the longest palindromic substring, and how do you compute each?
MediumDynamic programming
Technical
Show model answer
A subsequence may skip characters; a substring must be contiguous. For 'agbdba' the longest palindromic subsequence is 'abdba' (length 5) but the longest palindromic substring is 'bdb' (length 3). Subsequence DP: L[i][j] = L[i+1][j−1] + 2 if s[i] = s[j], else max(L[i+1][j], L[i][j−1]); O(n²) time and O(n²) space (O(n) with rolling rows). It equals the LCS of s and its reverse.
For the substring, expand around each of the 2n − 1 centres while the characters match: O(n²) time, O(1) space, and simpler than the O(n²) boolean DP table. Manacher's algorithm finds it in O(n) by reusing mirrored palindrome radii.