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"]

**Hint 1**
Try building a two-dimensional array of the longest common subsequences of substring pairs of the input strings. Let the rows of the array represent substrings of the second input string str2. Let the first row represent the empty string. Let each row i thereafter represent the substrings of str2 from 0 to i, with i excluded. Let the columns similarly represent the first input string str1.

**Hint 2**
Build up the array mentioned in Hint #1 one row at a time. In other words, find the longest common subsequences for all the substrings of str1 represented by the columns and the empty string represented by the first row, then for all the substrings of str1 represented by the columns and the first letter of str2 represented by the second row, etc., until you compare both full strings. Find a formula that relates the longest common subsequence at any given point to previous subsequences.

**Hint 3**
Do you really need to build and store subsequences at each point in the two-dimensional array mentioned in Hint #1? Try storing booleans to determine whether or not a letter at a given point in the two-dimensional array is part of the longest common subsequence as well as pointers to determine what should come before this letter in the final subsequence. Use these pointers to backtrack your way through the array and to build up the longest common subsequence at the end of your algorithm.

**Optimal Space & Time Complexity**
O(nm) time | O(nm) space - where n and m are the lengths of the two input strings

# O(nm*min(n, m)) time | O(nm*min(n, m)) space DEFINE FUNCTION longestCommonSubsequence(str1, str2): SET lcs TO [[[] FOR x IN range(len(str1) + 1)] FOR y IN range(len(str2) + 1)] FOR i IN range(1, len(str2) + 1): FOR j IN range(1, len(str1) + 1): IF str2[i - 1] EQUALS str1[j - 1]: SET lcs[i][j] TO lcs[i - 1][j - 1] + [str2[i - 1]] ELSE: SET lcs[i][j] TO max(lcs[i - 1][j], lcs[i][j - 1], key=len) RETURN lcs[-1][-1]

# O(nm*min(n, m)) time | O((min(n, m))^2) space DEFINE FUNCTION longestCommonSubsequence(str1, str2): SET small TO str1 IF len(str1) < len(str2) else str2 SET big TO str1 IF len(str1) >= len(str2) else str2 SET evenLcs TO [[] FOR x IN range(len(small) + 1)] SET oddLcs TO [[] FOR x IN range(len(small) + 1)] FOR i IN range(1, len(big) + 1): IF i % 2 EQUALS 1: SET currentLcs TO oddLcs SET previousLcs TO evenLcs ELSE: SET currentLcs TO evenLcs SET previousLcs TO oddLcs FOR j IN range(1, len(small) + 1): IF big[i - 1] EQUALS small[j - 1]: SET currentLcs[j] TO previousLcs[j - 1] + [big[i - 1]] ELSE: SET currentLcs[j] TO max(previousLcs[j], currentLcs[j - 1], key=len) RETURN evenLcs[-1] IF len(big) % 2 EQUALS 0 else oddLcs[-1]

# O(nm) time | O(nm) space DEFINE FUNCTION longestCommonSubsequence(str1, str2): SET lcs TO [[[None, 0, None, None] FOR x IN range(len(str1) + 1)] FOR y IN range(len(str2) + 1)] FOR i IN range(1, len(str2) + 1): FOR j IN range(1, len(str1) + 1): IF str2[i - 1] EQUALS str1[j - 1]: SET lcs[i][j] TO [str2[i - 1], lcs[i - 1][j - 1][1] + 1, i - 1, j - 1] ELSE: IF lcs[i - 1][j][1] > lcs[i][j - 1][1]: SET lcs[i][j] TO [None, lcs[i - 1][j][1], i - 1, j] ELSE: SET lcs[i][j] TO [None, lcs[i][j - 1][1], i, j - 1] RETURN buildSequence(lcs) DEFINE FUNCTION buildSequence(lcs): SET sequence TO [] SET i TO len(lcs) - 1 SET j TO len(lcs[0]) - 1 WHILE i != 0 and j != 0: SET currentEntry TO lcs[i][j] IF currentEntry[0] is not None: sequence.append(currentEntry[0]) SET i TO currentEntry[2] SET j TO currentEntry[3] RETURN list(reversed(sequence))

# O(nm) time | O(nm) space DEFINE FUNCTION longestCommonSubsequence(str1, str2): SET lengths TO [[0 FOR x IN range(len(str1) + 1)] FOR y IN range(len(str2) + 1)] FOR i IN range(1, len(str2) + 1): FOR j IN range(1, len(str1) + 1): IF str2[i - 1] EQUALS str1[j - 1]: SET lengths[i][j] TO lengths[i - 1][j - 1] + 1 ELSE: SET lengths[i][j] TO max(lengths[i - 1][j], lengths[i][j - 1]) RETURN buildSequence(lengths, str1) DEFINE FUNCTION buildSequence(lengths, string): SET sequence TO [] SET i TO len(lengths) - 1 SET j TO len(lengths[0]) - 1 WHILE i != 0 and j != 0: IF lengths[i][j] EQUALS lengths[i - 1][j]: i -= 1 ELSEIF lengths[i][j] EQUALS lengths[i][j - 1]: j -= 1 ELSE: sequence.append(string[j - 1]) i -= 1 j -= 1 RETURN list(reversed(sequence))

Previous Article

Longest Increasing SubsequenceNext Article

Line Through PointsQuick Sort

January 30, 2022

1 min

Selection Sort

January 28, 2022

1 min

Insertion Sort

January 27, 2022

1 min

Bubble Sort

January 26, 2022

1 min

Quick Links

Legal Stuff