bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
Medium2-D Dynamic ProgrammingLC 1143

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 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.

Asked at 10 companies
AmazonBloombergBytedance
Hints
  • 1.Think about what data structure fits Longest Common Subsequence
  • 2.Consider the brute force complexity and how to optimize
  • 3.Can you trade space for time?
LeetCodeNeetCode