Skip to interview prep
Apexed

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.

What is the difference between the longest palindromic subsequence and the longest palindromic substring, and how do you compute each — Data structures & algori