1143. Longest Common Subsequence

Problem¶

Given two strings, return the length of their longest subsequence that appears in both while preserving character order.

text1 = "abcde", text2 = "ace"
longest common subsequence = "ace"
output = 3

Key trick¶

Use dynamic programming on pairs of prefixes; when characters match, extend the diagonal result, otherwise keep the best result from excluding one character. Since each row depends only on the previous row, one array is sufficient.

Trap¶

When compressing to one dimension, preserve the old diagonal value before overwriting the current cell. Also start processing at the first actual character, not index zero with text1[i - 1], which accidentally reads the final character.

Why is it interesting?¶

It demonstrates how a natural two-dimensional recurrence can be reduced from \(O(mn)\) space to \(O(\min(m,n))\) space without changing its time complexity.

Python solution¶

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        # Use the shorter string for the DP array.
        if len(text1) < len(text2):
            text1, text2 = text2, text1

        dp = [0] * (len(text2) + 1)

        for ch1 in text1:
            # Value from the previous row and previous column.
            prev_diag = 0

            for j, ch2 in enumerate(text2, 1):
                # Save the previous row's value before overwriting it.
                above = dp[j]

                if ch1 == ch2:
                    dp[j] = prev_diag + 1
                else:
                    dp[j] = max(dp[j], dp[j - 1])

                prev_diag = above

        return dp[-1]

Time: \(O(mn)\)
Space: \(O(\min(m,n))\)

Comment on my solution¶

The two-dimensional solution is correct, clear, and already a strong interview answer with \(O(mn)\) time and space.

The compressed solution has an off-by-one error:

for i in range(len(text1) + 1):

At i == 0, text1[i - 1] becomes text1[-1], so the last character is processed as a fake initial row and can inflate the result. Starting at 1, or iterating directly over the characters as in the solution above, fixes it. Your prev_diag update logic is otherwise correct.

# Ideas:
# - it feels 2 DP on prefixes
#   - dp[i][j] longest common subsquence between prefixes s[:i] and t[:j]
#   - dp[m][n] is the answer
#        "" a ac ace
#    ""  0  0 0  0
#     a  0  1 1  1
#    ab  0  1 1  1
#   abc  0  1 2  2
#  abcd  0  1 2  2
# abcde  0  1 2  3
# - as dp[i][j] depends only on previous row
#   - this 2D DP could be reduced to 1D DP

# WORKS
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        m, n = len(text1), len(text2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i][j-1], dp[i-1][j])
        return dp[m][n]

Solution().longestCommonSubsequence("abcde", "ace")

# Wrong Answer: 46/49 testcases passed
# "whydynkfslsrmvyhonyjenyrenojofafmnafmfyhyjebwhqpwh", "ctqdkfctanypmxqxktqfwfgnwjqpsbgpydovufgfqbyvqpufujy"
# Output: 14
# Expected: 13
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        if len(text1) < len(text2):
            text1, text2 = text2, text1
        n = len(text2)
        dp = [0] * (n + 1)
        for i in range(len(text1) + 1):
            prev_diag = dp[0]
            for j in range(1, n + 1):
                diag = dp[j]
                if text1[i - 1] == text2[j - 1]:
                    dp[j] = prev_diag + 1
                else:
                    dp[j] = max(dp[j - 1], dp[j])
                prev_diag = diag
        return dp[-1]

Solution().longestCommonSubsequence("abcde", "ace")
Solution().longestCommonSubsequence("bsbininm", "jmjkbkjkv")