🚀 Phases 1–5 are live — Days 1–17 cover the foundations and the algorithmic patterns. See the roadmap →
Day 14 - Dynamic ProgrammingPractice QuestionsLongest Common Subsequence

Longest Common Subsequence medium

Description

Given two strings text1 and text2, return the length of their longest common subsequence. If there’s no common subsequence, return 0.

A subsequence of a string is a new string generated from the original by deleting some characters (possibly none) without changing the order of the remaining characters. A common subsequence of two strings is one that’s a subsequence of both.

Examples

> Case 1:
    text1 = "abcde",  text2 = "ace"
    Output: 3
    Explanation: LCS = "ace".
 
> Case 2:
    text1 = "abc",  text2 = "abc"
    Output: 3
 
> Case 3:
    text1 = "abc",  text2 = "def"
    Output: 0

Constraints

  • 1 <= text1.length, text2.length <= 1000
  • Both strings consist of lowercase English characters.

State design

  1. What am I computing? dp[i][j] = length of the LCS of the first i characters of text1 and the first j characters of text2.
  2. Dimensions? Two.
  3. Base cases? dp[0][j] = dp[i][0] = 0 (empty string vs anything = 0).
  4. Transition? Look at the last characters of the two prefixes:
    • Match: text1[i - 1] == text2[j - 1]. Drop both and extend: dp[i][j] = dp[i - 1][j - 1] + 1.
    • Mismatch: drop one character from either side, take the better: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).
  5. Order? Row-major: increasing i, increasing j.
  6. Answer? dp[n][m].

Why is the mismatch branch max(dp[i - 1][j], dp[i][j - 1])? Because a character that doesn’t match can’t be part of the LCS, so we must drop it from at least one side. We try both — drop from text1 (the dp[i - 1][j] branch) and drop from text2 (the dp[i][j - 1] branch) — and take whichever gives more.

Code

Space-optimized version

dp[i][j] only needs the previous row plus the cell to its left → roll on two rows for O(m) space.

Analysis

  • Time: O(n × m).
  • Space: O(n × m) for the basic version; O(m) for the rolling-row version.

Same skin

  • Shortest Common Supersequence (length): n + m − LCS.
  • Delete Operation for Two Strings: n + m − 2 × LCS.
  • Longest Palindromic Subsequence: LCS of s with reverse(s).
  • Distinct Subsequences: same state, different operator (count of ways to embed s2 in s1).
Longest Increasing Subsequence0/1 Knapsack