LCS (Longest Common Subsequence)

Medium

Find the longest subsequence common to both strings.

📊 Complexity

Type	Value
Best	O(n×m)
Average	O(n×m)
Worst	O(n×m)
Space	O(n×m)

🏷️ Tags

DPStringSubsequence

📖 Introduction

LCS finds the longest subsequence common to two strings while maintaining order. A "subsequence" doesn't need to be contiguous - just keep the original order.

1/45

🎯Longest Common Subsequence

Find the longest subsequence common to both strings! • String 1: "EARTH" • String 2: "HEART" "Subsequence" = Keep order, but not necessarily consecutive!

🔒

LCS (Longest Common Subsequence)

Medium

LCS (Longest Common Subsequence)

Find the longest subsequence common to both strings.

📊 Complexity

Type	Value
Best	O(n×m)
Average	O(n×m)
Worst	O(n×m)
Space	O(n×m)

🏷️ Tags

DPStringSubsequence

📖 Introduction

LCS finds the longest subsequence common to two strings while maintaining order. A "subsequence" doesn't need to be contiguous - just keep the original order.

1/45

🎯Longest Common Subsequence

Find the longest subsequence common to both strings! • String 1: "EARTH" • String 2: "HEART" "Subsequence" = Keep order, but not necessarily consecutive!

🔒

🎯Longest Common Subsequence