How do you solve Longest Common Subsequence on LeetCode?

Longest Common Subsequence (LeetCode #1143) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m * n) time complexity and O(m * n) space complexity. Key insight: Dynamic programming is a powerful technique for optimization problems.

What is the brute force solution for Longest Common Subsequence?

The brute force approach for Longest Common Subsequence is Brute Force, with O(2^n) time complexity and O(2^n) space complexity. The brute force approach involves generating all possible subsequences of both strings and checking for the longest common one. This is straightforward but inefficient as it explores all combinations. The optimal Optimal Solution approach improves this to O(m * n).

What algorithm or data structure is used to solve Longest Common Subsequence?

Longest Common Subsequence uses the following concepts: String, Dynamic Programming. The recommended patterns to study are: Dynamic Programming, Recursion.

What are the interview tips for Longest Common Subsequence?

Explain your thought process clearly before jumping into coding. Discuss edge cases and how your solution handles them. Practice coding the DP approach to become comfortable with it.

What are common mistakes when solving Longest Common Subsequence?

Not initializing the DP array correctly. Forgetting to handle base cases in DP.

#1143

Longest Common Subsequence

Medium

StringDynamic ProgrammingDynamic ProgrammingRecursion

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(2^n)	O(m * n)
Space	O(2^n)	O(m * n)

💡

Intuition

Time O(m * n)Space O(m * n)

The optimal solution uses dynamic programming to build a table that stores the lengths of common subsequences for substrings of text1 and text2. This avoids redundant calculations and efficiently finds the solution.

⚙️

Algorithm

4 steps

1Step 1: Create a 2D DP array with dimensions (len(text1)+1) x (len(text2)+1) initialized to 0.
2Step 2: Iterate through each character of text1 and text2, updating the DP array based on matches.
3Step 3: If characters match, set DP[i][j] = DP[i-1][j-1] + 1; otherwise, set DP[i][j] = max(DP[i-1][j], DP[i][j-1]).
4Step 4: The value at DP[len(text1)][len(text2)] will be the length of the longest common subsequence.

solution.py10 lines

1def longestCommonSubsequence(text1, text2):
2    m, n = len(text1), len(text2)
3    dp = [[0] * (n + 1) for _ in range(m + 1)]
4    for i in range(1, m + 1):
5        for j in range(1, n + 1):
6            if text1[i - 1] == text2[j - 1]:
7                dp[i][j] = dp[i - 1][j - 1] + 1
8            else:
9                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
10    return dp[m][n]

ℹ

Complexity note: The time complexity is O(m * n) because we fill a 2D array of size m x n, where m and n are the lengths of the two strings. Each cell in the array is computed in constant time.

1Dynamic programming is a powerful technique for optimization problems.
2Understanding the problem's structure helps in formulating the DP solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.