dynamic-programming · Problem 3 of 5
Longest Common Subsequence
Amazon
Google
Netflix
MicrosoftGiven two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
longestCommonSubsequence("abcde", "ace") -> 3 // "ace"
longestCommonSubsequence("abc", "abc") -> 3 // "abc"
longestCommonSubsequence("abc", "def") -> 0Your solution
Runs your code and animates it without grading anything. Change the input to see what it does on a case the tests do not cover.
Tests
5 cases, 2 hidden| call | type | expected | result |
|---|---|---|---|
| longestCommonSubsequence("abcde", "ace") | standard subsequence | 3 | — |
| longestCommonSubsequence("abc", "abc") | identical strings | 3 | — |
| longestCommonSubsequence("abc", "def") | no common characters | 0 | — |
| withheld | hidden | withheld | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Complexity
- target time
- O(m * n)
- target space
- O(m * n)
Iterating over the 2D grid of size (m+1) x (n+1) where each subproblem takes O(1) state transitions.
Hints
Stuck? Hints open one at a time, each giving a little more away.
3 hints left