Question

How to find the length of the longest common subsequence (LCS) in two strings with Python

Answer 1

def lcs(s1, s2, s1_len, s2_len):
    if s1_len == 0 or s2_len == 0:
        return 0
    elif s1[s1_len - 1] == s2[s2_len - 1]:
        return 1 + lcs(s1, s2, s1_len - 1, s2_len - 1)
    else:
        return max(lcs(s1, s2, s1_len, s2_len - 1), lcs(s1, s2, s1_len - 1, s2_len))


s1 = "accyrb"
s2 = "cyxyazb"

print("The length of LCS is:", lcs(s1 , s2, len(s1), len(s2)))


'''
run:

The length of LCS is: 3

'''

 

70+ SQL courses for beginners and professionals

Answer 2

"""
This program computes BOTH:
  1. The length of the Longest Common Subsequence (LCS)
  2. The actual LCS subsequence

It uses an efficient dynamic‑programming algorithm:
    Time:  O(n * m)
    Space: O(n * m)

dp[i][j] stores the LCS length between:
    s1[0..i-1] and s2[0..j-1]

Recurrence:
    If characters match:
        dp[i][j] = dp[i-1][j-1] + 1
    Else:
        dp[i][j] = max(dp[i-1][j], dp[i][j-1])

After filling the DP table, we reconstruct the LCS by
walking backwards from dp[n][m].
"""

def lcs(s1: str, s2: str):
    """Return both LCS length and the actual LCS subsequence."""
    n, m = len(s1), len(s2)

    # Create DP table initialized with zeros
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    # Fill DP table
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if s1[i - 1] == s2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # Reconstruct the LCS sequence
    length = dp[n][m]
    lcs_chars = []

    i, j = n, m
    while i > 0 and j > 0:
        if s1[i - 1] == s2[j - 1]:
            # Character is part of LCS
            lcs_chars.append(s1[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] > dp[i][j - 1]:
            i -= 1  # Move up
        else:
            j -= 1  # Move left

    # We built the LCS backwards → reverse it
    lcs_string = "".join(reversed(lcs_chars))

    return length, lcs_string


def main():
    s1 = "AGGTAB"
    s2 = "GXTXAYB"

    length, sequence = lcs(s1, s2)

    print("String 1:", s1)
    print("String 2:", s2)
    print("Length of LCS:", length)
    print("LCS sequence:", sequence)


if __name__ == "__main__":
    main()


"""
run:

String 1: AGGTAB
String 2: GXTXAYB
Length of LCS: 4
LCS sequence: GTAB

"""

 

70+ SQL courses for beginners and professionals