1143. Longest Common Subsequence

Longest Common Subsequence (LeetCode 1143) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Dynamic Programming (DP) Patterns pattern, in the 2D Array (Longest Common Subsequence - LCS) subpattern.

• Blind 75 · #60 of 75 · 2-D Dynamic Programming
• NeetCode 150 · #112 of 150 · 2-D Dynamic Programming
• NeetCode 250 · #194 of 250 · 2-D Dynamic Programming

How to solve Longest Common Subsequence

Longest Common Subsequence is a Longest Common Subsequence problem, part of Dynamic Programming (DP) Patterns. Find longest common subsequence between two strings using 2D DP.

Work towards the solution in these steps:

1. Try dynamic programming. DP[i][j] represents the longest common subsequence of text1[0 ... i] & text2[0 ... j].
2. DP[i][j] = DP[i - 1][j - 1] + 1 , if text1[i] == text2[j] DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]) , otherwise

The reference solution runs in O(m * n) time and O(min(m, n)) space.

The Longest Common Subsequence solution and editorial walks through the full approach with reference code.

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.

- For example, "ace" is a subsequence of "abcde".

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.

Topics and companies

Topics: String, Dynamic Programming.

Reported in interviews at Amazon, eBay, Google, Microsoft.

How to practise Longest Common Subsequence on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(min(m, n)) space.

Open Longest Common Subsequence in the code editor, or read the Longest Common Subsequence editorial for a worked solution with its approach and complexity analysis.

Where Longest Common Subsequence sits in the DSA pattern sheet

• Dynamic Programming (DP) Patterns pattern guide
• 2D Array (Longest Common Subsequence - LCS) subpattern
• The full DSA patterns sheet

Problems related to Longest Common Subsequence

Other problems that use the same 2D Array (Longest Common Subsequence - LCS) and Dynamic Programming (DP) Patterns techniques:

• Distinct Subsequences — Hard, same subpattern
• Minimum Insertion Steps to Make a String Palindrome — Hard, same subpattern
• Shortest Common Supersequence — Hard, same subpattern
• Best Time to Buy and Sell Stock — Easy, same pattern
• Best Time to Buy and Sell Stock II — Medium, same pattern
• Best Time to Buy and Sell Stock III — Hard, same pattern

Longest Common Subsequence FAQ