Longest Common Subsequence | Leetcode 1143 | All DP Approach

Given two strings text1 and text2, find the length of their Longest Common Subsequence (LCS). A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. Return the length of the LCS.

Here’s the [Problem Link] to begin with.

Example 1

Input:  text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The LCS is "ace" with length 3.

Example 2

Input:  text1 = "abc", text2 = "abc"
Output: 3
Explanation: The LCS is "abc" with length 3.

Goal: compute only the length of the LCS, not the subsequence itself.

Recursion

Intuition and Approach

Use pure recursion on indices (ind1, ind2) considering prefixes text1[0..ind1] and text2[0..ind2]:

• If either index is out of bounds, LCS length is 0.
• If characters match, take 1 plus LCS of both indices decremented.
• Otherwise, take the maximum of skipping one character from either string.

This explores all possibilities, but recomputes many subproblems.

Code Implementation

class Solution:
    def solve(self, ind1, ind2, text1, text2):
        if ind1 < 0 or ind2 < 0:
            return 0
        if text1[ind1] == text2[ind2]:
            return 1 + self.solve(ind1 - 1, ind2 - 1, text1, text2)
        return 0 + max(
            self.solve(ind1 - 1, ind2, text1, text2),
            self.solve(ind1, ind2 - 1, text1, text2),
        )

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)
        return self.solve(n - 1, m - 1, text1, text2)

Code explanation

• Base case handles when a prefix becomes empty.
• On match, both indices move left and add 1.
• On mismatch, try dropping one character from either side and take the best.

Time and Space Complexity

• Precise: Exponential time due to overlapping subproblems; recursion depth up to O(n + m) so space O(n + m).
• Simplified: Time exponential, space linear in depth.

Conclusion

Simple and clear, but not practical for larger inputs because of repeated work.

Memoization

Intuition and Approach

Cache results for each (ind1, ind2) to avoid recomputation. Same transitions as recursion, but store answers in a 2D table initialized to -1.

Code Implementation

class Solution:
    def solve(self, ind1, ind2, text1, text2, dp):
        if ind1 < 0 or ind2 < 0:
            return 0
        if dp[ind1][ind2] != -1:
            return dp[ind1][ind2]
        if text1[ind1] == text2[ind2]:
            dp[ind1][ind2] = 1 + self.solve(ind1 - 1, ind2 - 1, text1, text2, dp)
            return dp[ind1][ind2]
        dp[ind1][ind2] = 0 + max(
            self.solve(ind1 - 1, ind2, text1, text2, dp),
            self.solve(ind1, ind2 - 1, text1, text2, dp),
        )
        return dp[ind1][ind2]

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)
        dp = [[-1 for _ in range(m)] for _ in range(n)]
        return self.solve(n - 1, m - 1, text1, text2, dp)

Code explanation

• dp[ind1][ind2] holds LCS length for prefixes ending at ind1, ind2.
• Before computing, check cache; after computing, store and return.

Time and Space Complexity

• Precise: Each state computed once, states count n*m, per state O(1) work, so O(n*m) time and O(n*m) space for the table and recursion stack O(n + m).
• Simplified: O(n*m) time, O(n*m) space.

Conclusion

Efficient and easy to implement, suitable for typical constraints.

Memoization with 1-based shifted indices

Intuition and Approach

Shift indices so DP table dimensions are (n+1) x (m+1) with base row and column as zeros. This mirrors tabulation boundaries and simplifies transitions.

Code Implementation

class Solution:
    def solve(self, ind1, ind2, text1, text2, dp):
        if ind1 == 0 or ind2 == 0:
            return 0
        if dp[ind1][ind2] != -1:
            return dp[ind1][ind2]
        if text1[ind1 - 1] == text2[ind2 - 1]:
            dp[ind1][ind2] = 1 + self.solve(ind1 - 1, ind2 - 1, text1, text2, dp)
            return dp[ind1][ind2]
        dp[ind1][ind2] = 0 + max(
            self.solve(ind1 - 1, ind2, text1, text2, dp),
            self.solve(ind1, ind2 - 1, text1, text2, dp),
        )
        return dp[ind1][ind2]

    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n = len(text1)
        m = len(text2)
        dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]
        return self.solve(n, m, text1, text2, dp)

Code explanation

• Base cases live at row 0 or column 0, which cleanly represent empty prefixes.
• Character access uses ind1 - 1 and ind2 - 1 to map back to 0-based strings.

Time and Space Complexity

Same as standard memoization: O(n*m) time and O(n*m) space.

Conclusion

A notational variant that aligns naturally with bottom-up DP.

Tabulation

Intuition and Approach

Bottom-up DP fills a table dp[ind1][ind2] where:

• dp[0][*] = dp[*][0] = 0 for empty prefixes.
• If characters match, dp[i][j] = 1 + dp[i-1][j-1]; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

Code Implementation

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

Code explanation

• Initializes first row and column to zero representing empty strings.
• Fills the table row by row based on the recurrence.
• The answer is at dp[n][m].

Time and Space Complexity

• Precise: Filling n*m cells with O(1) work each gives O(n*m) time. Storing the full table costs O(n*m) space.
• Simplified: O(n*m) time and space.

Conclusion

Deterministic and iterative. Preferred when reconstructing the subsequence, since the full table enables backtracking.

Tabulation (Space Optimization)

Intuition and Approach

Observation: dp[i][*] depends only on dp[i-1][*] and the previous cell in the current row. Hence store only two rows:

• prev for row i-1
• curr for row i

Code Implementation

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

Code explanation

• prev[j] holds results for the previous row, curr[j] for the current row.
• Update curr left to right using prev[j-1], prev[j], and curr[j-1].
• Final answer sits in prev[m] after the last row.

Time and Space Complexity

• Precise: O(n*m) time, O(m) auxiliary space for the rolling rows.
• Simplified: O(n*m) time, O(min(n, m)) space if you roll along the shorter string.

Conclusion

Best practical version for length-only LCS when memory matters. Same complexity in time as full tabulation with significantly reduced space.

Final takeaway

• Recursion is conceptually simple but exponential.
• Memoization upgrades to O(n*m) by caching.
• Shifting indices to 1-based aligns well with tabulation.
• Tabulation offers iterative clarity and is useful for reconstruction.
• Space-optimized tabulation keeps time O(n*m) while reducing space to O(min(n, m)).

Choose memoization or tabulation for typical constraints. Use the space-optimized DP when memory is tight and you only need the LCS length.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.