L36 · DP IV — Subsequences (LIS / LCS)

Series: LeetCode — From Basics to Interview-Ready · Session 36 / 65 · Phase 2 · Dynamic programming

Prerequisites

You need L33–L35: what a DP state is, how a recurrence is derived, and the memo→table transition. If "define the state in one English sentence" does not yet feel automatic, re-do L33 first. Everything here is that skill applied to two specific state shapes.

Watch first (skim before the session)

Why this session exists

Two problems generate an entire family. Longest Increasing Subsequence (LIS) asks: inside one array, what is the longest chain that keeps going up? Longest Common Subsequence (LCS) asks: across two strings, what is the longest sequence you can read off both, in order, without rearranging?

Once you can write both from memory, a surprising number of "new" problems collapse into one of them plus a twist: Longest Palindromic Subsequence is just LCS of a string with its own reverse. Edit Distance (L40) is LCS with a cost twist. Russian Doll Envelopes is LIS after a sort. Maximum Length of Pair Chain is LIS in disguise. The leverage here is enormous — two templates unlock a dozen mediums.

Blank-file warm-up

Five minutes, empty file, no notes. Write both cores from memory:

LIS:  dp[i] = 1 + max(dp[j] for j < i if a[j] < a[i]), else 1
LCS:  dp[i][j] = dp[i-1][j-1] + 1        if a[i-1] == b[j-1]
                 max(dp[i-1][j], dp[i][j-1])   otherwise

If you cannot reproduce these cold, you do not know the session yet. Review, then start.

LIS from first principles

def length_of_lis(nums: list[int]) -> int:
    n = len(nums)
    dp = [1] * n                       # every element is a chain of length 1 by itself
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:      # strictly increasing
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp) if dp else 0        # answer can end anywhere
 
assert length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]) == 4   # [2,3,7,101] or [2,3,7,18]
assert length_of_lis([0, 1, 0, 3, 2, 3]) == 4
assert length_of_lis([7, 7, 7, 7]) == 1

That is O(n²). Interviewers who ask LIS almost always escalate to: can you do better than n²? The answer is O(n log n) with patience sorting.

from bisect import bisect_left
 
def length_of_lis_fast(nums: list[int]) -> int:
    tails: list[int] = []              # tails[k] = smallest possible tail of an increasing subseq of length k+1
    for x in nums:
        i = bisect_left(tails, x)      # first tail >= x
        if i == len(tails):
            tails.append(x)            # x extends the longest chain
        else:
            tails[i] = x               # x gives a smaller tail for a length-(i+1) chain
    return len(tails)                  # length of tails == LIS length
 
assert length_of_lis_fast([10, 9, 2, 5, 3, 7, 101, 18]) == 4

LCS from first principles

def lcs(a: str, b: str) -> int:
    m, n = len(a), len(b)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1        # matched last chars
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    return dp[m][n]
 
assert lcs("abcde", "ace") == 3        # "ace"
assert lcs("abc", "abc") == 3
assert lcs("abc", "def") == 0

The table has O(mn) cells, each filled in O(1), so O(mn) time and space. Space drops to O(n) with two rolling rows — a common follow-up.

Mental model

Memory hook

"LIS ends here; LCS matches the corner." LIS DP is anchored at the ending index (answer is max(dp), not dp[-1]). LCS DP branches on the corner diagonal cell (dp[i-1][j-1]) when the last characters match. Say the sentence out loud twice; it encodes the one detail people forget about each — where LIS's answer lives, and which neighbour LCS reaches on a match.

What interviewers actually ask

Real problems that live in this family, with what the interviewer is probing.

• LC300 · Longest Increasing Subsequence — Microsoft, Amazon, Google. They want the O(n²) DP first (proves you can define the state), then push for O(n log n). The probe: can you explain why patience sorting's tails length equals the LIS length? Follow-up: reconstruct the actual subsequence, or count how many distinct LIS there are (LC673).
• LC1143 · Longest Common Subsequence — Amazon, Adobe. The canonical 2D-string DP. Probe: the match-vs-mismatch branch and the base row/column. Follow-up: reduce space to O(min(m,n)) with rolling rows, or return the subsequence itself.
• LC516 · Longest Palindromic Subsequence — Amazon. The "aha" is that it equals LCS(s, reverse(s)). Probe: do you see the reduction, or do you reinvent an interval DP? Both are accepted; the reduction is the elegant answer.
• LC1035 · Uncrossed Lines — Amazon. Word-dressed LCS on two integer arrays. Probe: can you strip the story and recognise the parent problem?
• LC354 · Russian Doll Envelopes — Google, Amazon (Hard). Sort by width ascending, height descending, then LIS on heights. Probe: why the descending tie-break on height matters (it forbids stacking two envelopes of equal width). This one separates people who memorised LIS from people who understand it.
• LC673 · Number of Longest Increasing Subsequences — Amazon. LIS with a parallel count array. Probe: careful bookkeeping when dp[j] + 1 == dp[i] (add counts) vs > dp[i] (reset).

The universal escalation ladder here: n² DP → n log n (LIS) or O(min(m,n)) space (LCS) → reconstruct the actual sequence → count how many optimal sequences exist.

A worked reduction: Longest Palindromic Subsequence

Brute force would try every subsequence — exponential. The insight: a palindrome reads the same forwards and backwards, so the longest palindromic subsequence of s is exactly the longest subsequence common to s and reverse(s).

def longest_palindrome_subseq(s: str) -> int:
    return lcs(s, s[::-1])            # reuse the LCS we already wrote
 
assert longest_palindrome_subseq("bbbab") == 4   # "bbbb"
assert longest_palindrome_subseq("cbbd") == 2    # "bb"

• Complexity: O(n²) time and space (LCS of two length-n strings).
• Follow-up they escalate to: do it with an interval DP directly (dp[i][j] over substring s[i..j]) and reduce space. Both are fine; leading with the reduction shows range.

Tradeoff

In practice

Compilers and version-control diffs lean on LCS: the classic Unix diff computes a longest common subsequence of the two files' lines to find the minimal set of edits. That is why git diff output on a shuffled file can look surprisingly jumpy — the algorithm is optimising for the longest shared line-subsequence, not for what a human would call "the obvious change." Understanding LCS is understanding why diffs sometimes land where they do.

Practice queue

Solve in this order; log each as cold / warm / hint / failed for your spaced queue.

1. LC300 Longest Increasing Subsequence — the parent; do both n² and n log n.
2. LC1143 Longest Common Subsequence — the other parent; then add rolling-row space reduction.
3. LC516 Longest Palindromic Subsequence — reduce to LCS.
4. LC1035 Uncrossed Lines — LCS in disguise.
5. LC673 Number of Longest Increasing Subsequences — LIS with counts.
6. LC354 Russian Doll Envelopes — sort + LIS, the boss of this session.