< Back





1143. Longest Common Subsequence

Given two strings, we're asked to return their longest common subsequence - meaning the longest
string of characters we can create from the two strings maintaining the order of the characters.

Using dynamic programming, we can memoize our running count of the longest common subsequence in a
table. At each iteration through the 2D table, we can reuse the values we've calculated so far to
finalize our answer of the longest common subsequence.

We'll maintain a table of size T[m + 1][n + 1], where m and n are the lengths of the two strings,
initializing the table with 0 values. We'll iterate through the two strings, and at each step, we'll
check to see if the characters match for indices i - 1 and j - 1. If they do, we keep the answer from
the previous iteration and add 1 to it.

What's the previous iteration? It's the value at T[i - 1][j - 1] - the diagonal. We're essentially
saying that we're choosing this letter because it matches, and we want to update this point with the
decision that we made before reaching these matching characters.

If the characters don't match, we'll take the maximum of the value at T[i - 1][j] and T[i][j - 1].
We're essentially deciding whether to keep the character from the first or second string, whichever
one is provided the longest common subsequence so far.

Eventually we'll reach the end of the two strings, and the answer will be at T[m][n].

The solution is as follows:


  class Solution:
      def longestCommonSubsequence(self, text1: str, text2: str) -> int:
          m, n = len(text1), len(text2)
          T = [[0 for _ in range(n + 1)] for _ in range(m + 1)]

          for i in range(1, m + 1):
              for j in range(1, n + 1):
                  T[i][j] = T[i - 1][j - 1] + 1 if text1[i - 1] == text2[j - 1] else max(T[i - 1][j], T[i][j - 1])

          return T[m][n]


_ Time Complexity:

  O(m * n) - We iterate through a table of size m * n, where m and n are the lengths of the two
  strings.

_ Space Complexity:

  O(m * n) - We maintain a memoization table of size m * n.