Print Longest Common Subsequence
HardWalk the table backwards
Problem
Return the actual longest common subsequence of two strings (not just its length).
Build the LCS table, then walk backward from the corner, keeping letters that matched.
The idea
Build the usual LCS table, then start at the bottom-right and walk back: equal characters belong to the answer and move diagonally, otherwise move towards the larger neighbour. Reverse what you collected.
The trick
- Reconstruct from the completed table; do not try to build the string during filling.
- The collected characters come out reversed.
- O(m·n) to build, O(m+n) to walk back.
·
∅
A
C
∅
0
0
0
A
0
0
0
B
0
0
0
C
0
0
0
Step 1 of 8. LCS grid for "ABC" and "AC". Match → diagonal + 1, else the best of up/left.
1/8
Optimal
timeO(n·m)spaceO(n·m)
Match extends the diagonal.
1for (let i = 1; i <= n; i++)2 for (let j = 1; j <= m; j++)3 dp[i][j] = a[i-1] === b[j-1]4 ? dp[i-1][j-1] + 15 : Math.max(dp[i-1][j], dp[i][j-1]);Input
- grid
- 5 × 4
Memory
- at
- —
- cells marked
- 0
Output
- LCS
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- a = "abcde", b = "ace"
- Output:
- "ace"
- Explanation:
- The actual shared subsequence is ace.
Example 2
- Input:
- a = "bl", b = "yby"
- Output:
- "b"
- Explanation:
- Just b is shared.
Example 3
- Input:
- a = "abc", b = "abc"
- Output:
- "abc"
- Explanation:
- The whole string.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.