Katkat
Back

Compute longest common subsequence length

RokuSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This question tests the ability to solve the Longest Common Subsequence (LCS) problem using dynamic programming to optimize overlapping subproblems.

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.

Function Signature

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

Examples

Example 1:

  • Input: text1 = "abcde", text2 = "ace"
  • Output: 3
  • Explanation: The longest common subsequence is "ace", which has a length of 3.

Example 2:

  • Input: text1 = "abc", text2 = "abc"
  • Output: 3
  • Explanation: The longest common subsequence is "abc", which has a length of 3.

Example 3:

  • Input: text1 = "abc", text2 = "def"
  • Output: 0
  • Explanation: There is no common subsequence, so the result is 0.

Constraints

  • `1 = 1).
  • Strings with no common characters.
  • Strings that are identical.

Hints

Hint 1

Define a 2D array `dp[i][j]` representing the length of the longest common subsequence of `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]`, otherwise it is the maximum of `dp[i-1][j]` and `dp[i][j-1]`.

Hint 3

Consider optimizing the space complexity, as you only need the previous row of the DP table to calculate the current row.

Follow-up questions

  • How would you reconstruct the actual subsequence string instead of just returning its length?
  • Can you optimize the space complexity from O(N*M) to O(min(N, M))?
  • How would the solution change if you needed to find the longest common substring (where characters must be contiguous) instead of a subsequence?