{"id":994,"date":"2025-08-26T16:13:44","date_gmt":"2025-08-26T10:43:44","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=994"},"modified":"2025-08-26T16:13:46","modified_gmt":"2025-08-26T10:43:46","slug":"longest-palindromic-subsequence","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/longest-palindromic-subsequence\/","title":{"rendered":"Longest Palindromic Subsequence | Leetcode 516"},"content":{"rendered":"\n

Given a string s<\/code>, find the length of the longest palindromic subsequence<\/strong> in s<\/code>. A subsequence keeps relative order but is not required to be contiguous.<\/p>\n\n\n\n

A standard reduction is to compute the Longest Common Subsequence (LCS)<\/strong> between s<\/code> and its reverse rev(s)<\/code>. The LCS length equals the Longest Palindromic Subsequence length.<\/p>\n\n\n\n

Here’s the [Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n\n

Example 1<\/strong><\/p>\n\n\n\n

<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input<\/span>:  <\/span>s = "bbbab"<\/span><\/span>\nOutput<\/span>: <\/span>4<\/span><\/span>\nExplanation<\/span>: <\/span>One LPS is "bbbb" with length 4.<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
Example 2<\/strong><\/p>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
Input<\/span>:  <\/span>s = "cbbd"<\/span><\/span>\nOutput<\/span>: <\/span>2<\/span><\/span>\nExplanation<\/span>: <\/span>One LPS is "bb" with length 2.<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
\n\n\n\n
Intuition and Approach<\/h2>\n\n\n\n
    \n
  1. Convert LPS to LCS by setting s1 = s<\/code> and s2 = reverse(s)<\/code>.<\/li>\n\n\n\n
  2. Compute LCS length of s1<\/code> and s2<\/code> using any LCS technique.<\/li>\n\n\n\n
  3. The resulting LCS length is the answer to LPS.<\/li>\n<\/ol>\n\n\n\n
    Below are three implementations that follow this plan.<\/p>\n\n\n
    \n\t\t\t
    \n\t\t\t\t
    Content:<\/div>\n\t\t\t\t
    \n\t\t\t
    \n\t\t\t\u00a0[show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div>
    \n\t\t\t
    \n\t\t\t\t