Katkat
Back

Find length of longest common subsequence

TikTokMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to identify overlapping subproblems and optimal substructure by implementing a dynamic programming solution to find the length of the Longest Common Subsequence (LCS) between two strings.

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 is a subsequence that is common to both strings.

Function Signature

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

Constraints

  • 1 <= text1.length, text2.length <= 1000
  • The 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 length 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 constrained to length >= 1).
  • Strings with no common characters.
  • Strings that are identical.

Hints

Hint 1

Define a 2D array dp where dp[i][j] represents the length of the longest common subsequence of text1[0...i-1] and text2[0...j-1].

Hint 2

If text1[i-1] == text2[j-1], then dp[i][j] = 1 + dp[i-1][j-1], because we have found a matching character.

Hint 3

If the characters do not match, the value is the maximum of the result obtained by excluding either the current character of text1 or text2: max(dp[i-1][j], dp[i][j-1]).

Follow-up questions

  • How can you optimize the space complexity from O(N*M) to O(min(N, M))?
  • How would you modify the algorithm to reconstruct the actual subsequence string instead of just returning its length?
  • If you were tasked with finding the Longest Common Substring (where characters must be contiguous) instead of a subsequence, how would your DP approach change?