Log inSign up
mediumLeetCodeNot Started

Longest Common Subsequence

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Dynamic Programming
Solve on LeetCode
Lesson

Problem Statement

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters (e.g., "ace" is a subsequence of "abcde" while "aec" is not).

A common subsequence of two strings is a subsequence that is common to both strings.

### Example 1 - Input: text1 = "abcde", text2 = "ace" - Output: 3 - Explanation: The longest common subsequence is "ace" and its length is 3.

### Example 2 - Input: text1 = "abc", text2 = "abc" - Output: 3 - Explanation: The longest common subsequence is "abc" and its length is 3.

### Example 3 - Input: text1 = "abc", text2 = "def" - Output: 0 - Explanation: There is no such common subsequence, so the result is 0.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the quintessential 2D string matching recurrence.
  • Understand why matching elements forces diagonal transitions.
  • Space-optimize from O(m * n) to O(min(m, n)).

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Comparing two sequences for maximum length shared elements.
  • Non-contiguous matching allowed.
  • Order must be strictly preserved.

Algorithmic Decision Tree:

  • Match -> 1 + diagonal.
  • Mismatch -> max of top and left.

Connected Patterns:

Longest Common SubstringEdit DistanceShortest Common Supersequence

1. Recursive Exhaustive Search

Intuition

Check characters from end to start: if equal, add 1 and recurse on both prefixes; else branch into dropping one character from text1 or text2.

Algorithm

  1. Define dfs(i, j).
  2. If i == 0 or j == 0, return 0.
  3. If text1[i-1] == text2[j-1], return 1 + dfs(i-1, j-1).
  4. Return max(dfs(i-1, j), dfs(i, j-1)).
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <string>
3#include <algorithm>
4
5using namespace std;
6
7int dfs(int i, int j, const string& s1, const string& s2) {
8 if (i == 0 || j == 0) return 0;
9 if (s1[i - 1] == s2[j - 1]) {
10 return 1 + dfs(i - 1, j - 1, s1, s2);
11 }
12 return max(dfs(i - 1, j, s1, s2), dfs(i, j - 1, s1, s2));
13}
14
15int lcsRec(string text1, string text2) {
16 return dfs(text1.length(), text2.length(), text1, text2);
17}
18
19int main() {
20 string t1 = "abcde", t2 = "ace";
21 cout << "LCS (Recursive): " << lcsRec(t1, t2) << endl;
22 return 0;
23}

Time & Space Complexity

  • Time complexity: O(2^(m + n))
  • Space complexity: O(m + n) call stack

2. 2D Dynamic Programming Tabulation

Intuition

Build matrix dp[m + 1][n + 1] where dp[i][j] is LCS of text1[0..i-1] and text2[0..j-1].

Algorithm

  1. Let m = text1.length, n = text2.length.
  2. Create dp of size (m + 1) x (n + 1) filled with 0.
  3. For i = 1 to m:
  4. For j = 1 to n:
  5. If text1[i - 1] == text2[j - 1]:
  6. dp[i][j] = 1 + dp[i - 1][j - 1]
  7. Else:
  8. dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
  9. Return dp[m][n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8int longestCommonSubsequence2D(string text1, string text2) {
9 int m = text1.length(), n = text2.length();
10 vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
11
12 for (int i = 1; i <= m; i++) {
13 for (int j = 1; j <= n; j++) {
14 if (text1[i - 1] == text2[j - 1]) {
15 dp[i][j] = 1 + dp[i - 1][j - 1];
16 } else {
17 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
18 }
19 }
20 }
21 return dp[m][n];
22}
23
24int main() {
25 string t1 = "abcde", t2 = "ace";
26 cout << "LCS (2D DP): " << longestCommonSubsequence2D(t1, t2) << endl;
27 return 0;
28}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

3. 1D Array Space-Optimized DP

Intuition

Maintain a single array dp of size n + 1 with a scalar prev for diagonal values.

Algorithm

  1. Let m = text1.length, n = text2.length.
  2. Initialize dp of size n + 1 filled with 0.
  3. For i = 1 to m:
  4. prev = 0
  5. For j = 1 to n:
  6. temp = dp[j]
  7. If text1[i - 1] == text2[j - 1]:
  8. dp[j] = 1 + prev
  9. Else:
  10. dp[j] = max(dp[j], dp[j - 1])
  11. prev = temp
  12. Return dp[n].
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5
6using namespace std;
7
8int longestCommonSubsequenceOptimal(string text1, string text2) {
9 if (text1.length() < text2.length()) swap(text1, text2);
10 int m = text1.length(), n = text2.length();
11 vector<int> dp(n + 1, 0);
12
13 for (int i = 1; i <= m; i++) {
14 int prev = 0;
15 for (int j = 1; j <= n; j++) {
16 int temp = dp[j];
17 if (text1[i - 1] == text2[j - 1]) {
18 dp[j] = 1 + prev;
19 } else {
20 dp[j] = max(dp[j], dp[j - 1]);
21 }
22 prev = temp;
23 }
24 }
25 return dp[n];
26}
27
28int main() {
29 string t1 = "abcde", t2 = "ace";
30 cout << "LCS (Optimal 1D DP): " << longestCommonSubsequenceOptimal(t1, t2) << endl;
31 return 0;
32}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(min(m, n)) space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Recursive Suffix SearchO(2^(m + n))O(m + n)Exhaustive branching over matching characters.Redundant subproblem calls
2.2D TabulationO(m * n)O(m * n)Matrix grid storing prefix LCS lengths.Matrix allocation
3.1D Array Space OptimizedOptimalO(m * n)O(min(m, n))Single 1D array with prev diagonal scalar.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Confusing Subsequence (non-contiguous) with Substring (contiguous).

Pitfall 2:

Swapping indices in the 1D space optimization.

Crucial Edge Cases to Validate:

  • No matching characters: Output is 0.
  • Identical strings: Output is length of string.
  • Single character match: Output is 1.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. LCS is the foundation for: Diff utilities, Edit Distance, Shortest Common Supersequence, and Minimum Deletions/Insertions to transform strings. Mention these connections proactively.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does dp[i][j] = 1 + dp[i - 1][j - 1] when text1[i - 1] == text2[j - 1], rather than taking the max with dp[i-1][j] or dp[i][j-1]?

Back to DSA Sheet