Funcia
Lv.2dpstring

Longest Common Subsequence Length

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
0

Two explorers wrote down, in order, the first letter of every village they visited: explorer A's log is the string a and explorer B's log is the string b.

Return the length of the longest string that is a subsequence of both a and b (return 0 if they share no letter). A subsequence keeps the original order but need not be contiguous: "ace" is a subsequence of "abcde", "aec" is not.

Examples

abresult
"abcde""ace"3
"abc""def"0
"aggtab""gxtxayb"4

Example 1 — "ace" is common to both strings.

Example 2 — No letter appears in both strings.

Example 3 — "gtab" is a longest common subsequence.

Efficiency

This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.

Function signature

solution(a: string, b: string) → int

Constraints

  • 1≤1 \le a.length ≤2,000\le 2{,}000
  • 1≤1 \le b.length ≤2,000\le 2{,}000
  • a and b consist of lowercase English letters only.

Expected complexity

Time
O(NM)
Space
O(M)

Examples

abExpected
"abcde""ace"3
"abc""def"0
"aggtab""gxtxayb"4

Hint

Hint

Let dp[i][j] be the answer for the first i letters of a and the first j letters of b: if a[i-1] == b[j-1] then dp[i][j] = dp[i-1][j-1] + 1, otherwise max(dp[i-1][j], dp[i][j-1]). Plain branching recursion recomputes the same (i, j) pairs exponentially often; filling the table is O(NM)O(NM), and keeping only the previous row needs O(M)O(M) memory.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4014verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.