A subsequence keeps some characters of a string in their original order (not necessarily adjacent). Given two strings, print the length of the longest subsequence they share.
Constraints
- 1 ≤ length of each ≤ 2000
- Lowercase letters
Input and output
- Input
- Line 1: string a Line 2: string b
- Output
- One integer.
Examples
Input 1
abcde
aceOutput
3ace
Input 2
abc
defOutput
0Nothing shared.
Show hints
- Compare the last characters of the two prefixes.
Show the explanation
L[i][j] = LCS length of the first i characters of a and first j of b. If a[i−1] == b[j−1] then L[i][j] = L[i−1][j−1] + 1, else max(L[i−1][j], L[i][j−1]). Only the previous row is needed, so memory can be O(min(n, m)); time is O(n·m).
Original UniCircle question. Last reviewed 21 Oct 2026.