Longest Palindromic Subsequence

Longest Palindromic Subsequence

What is this problem about?

The Longest Palindromic Subsequence (LPS) interview question provides a string s and asks you to find the length of the longest palindromic subsequence within it. Unlike a substring, a subsequence allows you to delete characters from the original string. For instance, in the string "bbbab", the longest palindromic subsequence is "bbbb", which has a length of 4.

Why is this asked in interviews?

This is a classic Dynamic Programming problem and a staple in technical interviews. It tests a candidate's ability to define subproblems that shrink from two boundaries simultaneously. Interviewers use LPS to see if you understand how to build a 2D DP matrix where the state depends on the interval [left, right], which is fundamentally different from left-to-right linear DP problems.

Algorithmic pattern used

This problem is the textbook example of Interval Dynamic Programming. You define a 2D array dp[i][j], representing the length of the LPS within the substring from index i to index j.

• If s[i] == s[j], then those two characters match and form the outer shell of a palindrome. So, dp[i][j] = dp[i+1][j-1] + 2.
• If s[i] != s[j], they don't match. You must shrink the window from either the left or the right. So, dp[i][j] = max(dp[i+1][j], dp[i][j-1]).

Example explanation

String s = "bbbab". Length = 5. We initialize dp[i][i] = 1 because every single character is a palindrome of length 1. We check length 2 windows: "bb", "bb", "ba", "ab". Matches get 2, mismatches get max of inner parts. We check length 3 windows... Let's look at the window spanning the whole string i=0 to j=4 ("bbbab").

• s[0] == 'b', s[4] == 'b'. They match!
• Therefore, dp[0][4] = dp[1][3] + 2.
• What is dp[1][3]? That's the interval "bba".
• For "bba" (i=1, j=3), s[1] != s[3]. dp[1][3] = max(dp[2][3], dp[1][2]) = max(length of "ba", length of "bb").
• "bb" is a palindrome of length 2.
• So dp[1][3] = 2.
• Ultimately, dp[0][4] = 2 + 2 = 4. The maximum length is 4.

Common mistakes candidates make

A common trap is traversing the 2D DP matrix using standard row-by-row for loops (for i=0 to N, for j=0 to N). Because dp[i][j] depends on dp[i+1][j-1] (a row below it), standard iteration will look up values that haven't been calculated yet! You must iterate by the length of the interval, starting from length 1 up to length $N$, or iterate i backwards from $N$ down to 0.

Interview preparation tip

When studying the Longest Palindromic Subsequence coding pattern, recognize that it is mathematically identical to finding the Longest Common Subsequence (LCS) between the string s and its exact reverse, reverse(s). If you struggle with Interval DP, you can literally reverse the string and run the standard, easier LCS algorithm. Mentioning this dual approach in an interview demonstrates a deep, interconnected understanding of string algorithms.