Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Longest Common Subsequence

Dynamic Programmingmedium

Implement `lcs(a, b)` returning the length of the longest common subsequence of strings `a` and `b`.

Sample tests

Input: lcs("abcde", "ace")
Output: 3
Input: lcs("abc", "abc")
Output: 3

+ 1 hidden test run on Submit.

Hints

Common pitfalls
  • Confusing subsequence with substring (subsequence allows gaps).

Learning resources

  • Wikipedia: Dynamic programming
Approach & explanation (try first)

A 2D DP over prefixes gives the LCS length in O(m * n) time.

Loading...
⌘/Ctrl + Enter

Run your code to see results.