{"id":987,"date":"2025-08-22T16:52:32","date_gmt":"2025-08-22T11:22:32","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=987"},"modified":"2025-08-22T16:52:33","modified_gmt":"2025-08-22T11:22:33","slug":"print-the-longest-common-subsequence","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/print-the-longest-common-subsequence\/","title":{"rendered":"Print the Longest Common Subsequence | Build Table, Then Reconstruct"},"content":{"rendered":"\n

Given two strings text1<\/code> and text2<\/code>, the goal is to print one actual Longest Common Subsequence (LCS)<\/strong>, not just its length. An LCS is a sequence that appears in both strings in the same relative order, but not necessarily contiguously. If multiple LCS strings exist, returning any one of them is acceptable.<\/p>\n\n\n\n

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

<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
text1<\/span> = <\/span>"abcde"<\/span>, <\/span>text2<\/span> = <\/span>"ace"<\/span><\/span>\nLCS <\/span>length<\/span> = <\/span>3<\/span>, one LCS <\/span>is<\/span> <\/span>"ace"<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
<\/circle><\/circle><\/circle><\/g><\/svg><\/span><\/path><\/path><\/svg><\/span>
text1<\/span> = <\/span>"abc"<\/span>,<\/span> text2<\/span> = <\/span>"def"<\/span><\/span>\nLCS <\/span>length<\/span> = <\/span>0<\/span>,<\/span> LCS<\/span> <\/span>string<\/span> is <\/span>""<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n
\n\n\n\n
Intuition and Approach<\/h2>\n\n\n\n
The standard approach has two clear phases.<\/p>\n\n\n\n
    \n
  1. Compute the DP table of LCS lengths<\/strong>
    Build a table dp<\/code> of size (n+1) x (m+1)<\/code> where dp[i][j]<\/code> stores the LCS length for prefixes text1[:i]<\/code> and text2[:j]<\/code>.
    Transition:\n