HomeOur TeamContact
Longest Common Subsequence
Dynamic Programming
Longest Common Subsequence
Sameer
Sameer
May 20, 2021
1 min

Longest Common Subsequence

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

Hints

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

Solution 1

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

Solution 2

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

Solution 3

# 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))

Solution 4

# 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))

Tags

#Difficulty Hard#Algorithm
Previous Article
Longest Increasing Subsequence
Sameer

Sameer

Related Posts

Heap Sort
January 31, 2022
1 min
© 2022, All Rights Reserved.

Quick Links

Advertise with usAbout UsContact Us

Social Media