Longest common subsequence

Hard

Let's say you're given two strings. Find the longest common subsequence of the two strings.

The longest common subsequence of two strings is the length of the longest substring of string 1 that exists in the same order in string 2, regardless of the distance between the characters.

Here are some examples:

The longest common subsequence of cat and dog is 0.
The longest common subsequence of AABDF and BODLF is 2, (BD).
The longest common subsequence of CVBNC and COBONAC is 4, (CBNC).
The longest common subsequence of BLOG and OGBL is 2, (OG and BL).

Try it first

def lcs(a: str, b: str) -> int:
    # implement lcs
    return 0

1def lcs(a: str, b: str) -> int:
2    # implement lcs
3    return 0
4

Solution

8 Essential Recursion & Dynamic Programming Coding Interview Problems

Master Recursion & Dynamic Programming by trying the coding challenges below.

1.FibonacciEasy
2.Unique pathsMedium
3.KnapsackMedium
4.Subset sumMedium
5.Power setMedium
6.Coin changeMedium
7.Word breakHard
8.Longest common subsequenceHard

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.