Longest Common Subsequence Leetcode Problem 1143 [Python Solution]

Do you want to know how to solve the Longest Common Subsequence Leetcode problem efficiently? I do too because it is such a classic dynamic programming challenge.

By the end of this guide, you’ll have a solid Python solution to this problem.

Let’s dive right in!

Problem Overview

Question: Given two strings, text1 and text2, we want to find the length of their longest common subsequence.

If there is no common subsequence, we should return 0. A subsequence of a string is a new string formed from the original by deleting some (or none) of the characters without changing the relative order of the remaining characters.

For example, “ace” is a subsequence of “abcde.”

A common subsequence of two strings is a subsequence that appears in both strings.

Example 1:

Input:

text1 = "abcde"
text2 = "ace"

Output:

3

Explanation: The longest common subsequence is “ace,” with a length of 3.

Example 2:

Input:

text1 = "abc"
text2 = "abc"

Output:

3

Explanation: The longest common subsequence is “abc,” with a length of 3.

Example 3:

Input:

text1 = "abc"
text2 = "def"

Output:

0

Explanation: There is no common subsequence, so the result is 0.

Understanding the Constraints

Before we dive into the Python code solution, it’s essential to understand the constraints:

• 1 <= text1.length, text2.length <= 1000
• text1 and text2 consist of only lowercase English characters.

These constraints help us design an efficient solution without worrying about performance bottlenecks.

Longest Common Subsequence LeetCode Problem Solution

Now, let’s solve this problem step by step.

1. Bruteforce Approach

A simple but inefficient way to solve this problem is by generating all possible subsequences of both strings and comparing them.

We can then return the length of the longest common subsequence.

However, this approach has exponential time complexity and is not suitable for the given constraints.

Therefore, we’ll explore a more efficient dynamic programming approach.

2. An Efficient Approach with Dynamic Programming

We’ll use a 2D dynamic programming array to store the length of the longest common subsequence at each position in the two input strings.

We’ll initialize a grid dp, where dp[i][j] represents the length of the longest common subsequence between text1[0:i] and text2[0:j].

The dynamic programming algorithm works as follows:

• If text1[i] is equal to text2[j], we extend the common subsequence by one and set dp[i][j] = dp[i-1][j-1] + 1.

In this case, we take the diagonal value and add one.

• If the characters do not match, we have two choices:
  1. We can exclude text1[i] and find the longest common subsequence between text1[0:i-1] and text2[0:j].

This value is dp[i-1][j].
2. We can exclude text2[j] and find the longest common subsequence between text1[0:i] and text2[0:j-1].

This value is dp[i][j-1.

We take the maximum of these two choices and update dp[i][j] accordingly.

Finally, dp[-1][-1] will hold the length of the longest common subsequence between the entire strings text1 and text2, and we return this value.

Here’s the Python code for our efficient dynamic programming approach:

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

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

    return dp[0][0]

Time and Space Complexity

The time complexity of this solution is O(m * n), where m and n are the lengths of text1 and text2, respectively.

This is because we fill in a 2D grid of size m x n.

The space complexity is O(m * n) as well, as we store the grid with this size.

Reasoning Behind Our Approach

This dynamic programming approach leverages the concept of building the solution incrementally and utilizing previously computed values to find the longest common subsequence efficiently.

By considering each character’s match or mismatch, we create a path through the grid, ultimately reaching the desired result.

Related Interview Questions By Company:

• Remove Nth Node From End Of List LeetCode
• Word Search LeetCode
• Ones And Zeroes LeetCode

Related Interview Questions By Difficulty:

• Edit Distance LeetCode
• Longest Common Subsequence LeetCode
• Interleaving String LeetCode

Related Interview Questions By Category:

• Cheapest Flights Within K Stops LeetCode
• Unique Paths II LeetCode
• Invert Binary Tree LeetCode

Conclusion

In this guide, we’ve tackled the Longest Common Subsequence problem efficiently using dynamic programming.

We explored the problem, understood its constraints, and developed a Python solution that handles it within the given limits.

Dynamic programming is a powerful technique for solving various algorithmic challenges, and this problem serves as an excellent example of its application.

If you have any questions, suggestions, or want to explore more coding topics, please don’t hesitate to comment and engage with us.

Happy coding!

Question Link

Now that you have a solid solution to the Longest Common Subsequence problem, feel free to ask any questions or share your thoughts in the comments section.

Happy coding!