Katkat
Back

Find longest common subsequence length

TikTokSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to solve the Longest Common Subsequence (LCS) problem using dynamic programming, specifically focusing on building a 2D state table.

Problem: Longest Common Subsequence

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

A subsequence is a sequence that appears in the same relative order, but not necessarily contiguously. For example, "ace" is a subsequence of "abcde".

Function Signature

def longest_common_subsequence(text1: str, text2: str) -> int:

Constraints

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

Examples

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 = "def"
  • Output: 0
  • Explanation: There is no common subsequence, so the result is 0.

Edge Cases

  • Empty strings (though constraints imply length >= 1).
  • Strings with no common characters.
  • Strings that are identical.

Hints

Hint 1

Consider a 2D array `dp[i][j]` representing the LCS length for the prefixes `text1[0...i-1]` and `text2[0...j-1]`.

Hint 2

If characters `text1[i-1]` and `text2[j-1]` match, the value is `1 + dp[i-1][j-1]`.

Hint 3

If they do not match, the value is the maximum of `dp[i-1][j]` or `dp[i][j-1]`.

Follow-up questions

  • How can you optimize the space complexity of this solution from O(M*N) to O(min(M, N))?
  • How would you reconstruct the actual subsequence string instead of just returning its length?
  • What would change if you were asked to find the Longest Common Substring (where the sequence must be contiguous)?