Longest Common Subsequence

Category: Dynamic Programming

Difficulty: Hard

Description

Write a function that takes in two strings and returns their longest common subsequence.

A subsequence of a string is a set of characters that aren't necessarily adjacent in the string but that are in the same order as they appear in the string. For instance, the characters ["a", "c", "d"] form a subsequence of the string "abcd", and so do the characters ["b", "d"]. Note that a single character in a string and the string itself are both valid subsequences of the string.

You can assume that there will only be one longest common subsequence.

Sample Input

str1 = "ZXVVYZW"
str2 = "XKYKZPW"

Sample Output

["X", "Y", "Z", "W"]

Optimal Space & Time Complexity

O(nm) time | O(nm) space - where n and m are the lengths of the two input strings