beingsde
Sign In
Back to all DSA patterns
Dynamic Programming•Pattern: DP / 2D Table•Medium

Longest common subsequence (LCS)

Problem Intuition & Objective

Find the length of the longest subsequence common to two strings.

Time ComplexityO(m×n)
Optimal
Space ComplexityO(min(m,n))
Memory Bounds
Optimal Algorithmic Approach

2D DP table, space-optimizable to 1D.

Core Invariants & Edge Cases

  • dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]
  • Match: dp[i][j] = dp[i-1][j-1] + 1; else max(dp[i-1][j], dp[i][j-1])
  • Space-optimized to O(min(m,n)) with a single row
Previous ProblemHouse Robber — max sum of non-adjacent elementsNext Problem Edit distance (Levenshtein)

System Design & Architecture Roadmap

Coding interviews are only 50% of the bar. Master High-Level Design, distributed systems, and Object-Oriented LLD.

60+ HLD QuestionsSharding, caching, and real-time distributed systems.27 LLD BlueprintsObject-oriented design patterns with class diagrams.SDE Quick ReferenceLatency numbers and database selection matrix.