Subsequence DP

🎯 Subsequence DP: Finding Patterns in Sequences

The Story of the Treasure Hunter

Imagine you’re a treasure hunter with a magical map. The map has letters written in a row. Your job? Find hidden words by picking letters without changing their order.

You can skip letters, but you cannot rearrange them.

This is exactly what Subsequence DP does!

🧩 What is a Subsequence?

A subsequence is a sequence you get by deleting some (or no) characters from a string, without changing the order of remaining characters.

Simple Example

String: "ABCDE"

Some subsequences:

• "ACE" ✅ (skip B and D)
• "BD" ✅ (skip A, C, E)
• "ABCDE" ✅ (skip nothing)
• "" ✅ (skip everything)
• "CAB" ❌ (wrong order!)

Think of it like picking candies from a line without moving them around.

🔢 The Four Subsequence Problems

We’ll learn four treasure-hunting missions:

📝 1. Is Subsequence

The Mission

Question: Can string s be found inside string t (keeping order)?

Like asking: “Can I spell CAT by crossing out letters in SCRATCH?”

The Simple Idea

Use two fingers:

• Finger 1 on s (the word we want)
• Finger 2 on t (the big word)

Move finger 2 along t. When letters match, move finger 1 too.

If finger 1 reaches the end, we found all letters!

Python Code

def is_subsequence(s, t):
    # Two pointers
    i = 0  # Finger on s
    j = 0  # Finger on t

    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1  # Found a match!
        j += 1      # Always move in t

    # Did we find all letters?
    return i == len(s)

Walk-Through Example

s = "ace"
t = "abcde"

Step 1: i=0, j=0
  s[0]='a' == t[0]='a' ✅
  i → 1

Step 2: i=1, j=1
  s[1]='c' != t[1]='b'
  j → 2

Step 3: i=1, j=2
  s[1]='c' == t[2]='c' ✅
  i → 2

Step 4: i=2, j=3
  s[2]='e' != t[3]='d'
  j → 4

Step 5: i=2, j=4
  s[2]='e' == t[4]='e' ✅
  i → 3

i reached len(s)=3 → TRUE!

Time & Space

• Time: O(n) - one pass through t
• Space: O(1) - just two pointers

🏆 2. Longest Common Subsequence (LCS)

The Mission

Given two strings, find the longest word hiding in both of them.

Real-Life Example

DNA Sequence 1: "AGCAT"
DNA Sequence 2: "GAC"

Common letters (in order): "GAC" or "AC" or "GA"
Longest? "GAC" with length 3!

Wait, let’s check:

• G appears in both ✅
• A appears after G in both ✅
• C appears after A in both ✅

The DP Table Magic

We build a grid where each cell answers:

“What’s the LCS of first i letters of word1 and first j letters of word2?”

graph TD
    A["Compare last letters"] --> B{Match?}
    B -->|Yes| C["LCS = 1 + LCS without those letters"]
    B -->|No| D["LCS = max of skipping either letter"]

Python Code

def longest_common_subseq(text1, text2):
    m, n = len(text1), len(text2)

    # Create DP table with extra row/col
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # Fill the table
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                # Letters match! Add 1
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                # No match - take best option
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])

    return dp[m][n]

Visual Example

     ""  G   A   C
  "" [0] [0] [0] [0]
  A  [0] [0] [1] [1]
  G  [0] [1] [1] [1]
  C  [0] [1] [1] [2]
  A  [0] [1] [2] [2]
  T  [0] [1] [2] [2]

Answer: dp[5][3] = 2
LCS = "AC" or "GC"

The Rule

if text1[i] == text2[j]:
    dp[i][j] = dp[i-1][j-1] + 1
else:
    dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Time & Space

• Time: O(m × n)
• Space: O(m × n) - can optimize to O(n)

📈 3. Longest Increasing Subsequence (LIS)

The Mission

Find the longest sequence of numbers that keeps going up.

Real-Life Story

You’re stacking blocks. Each new block must be taller than the last. What’s the tallest tower you can build from a row of blocks?

Example

Numbers: [10, 9, 2, 5, 3, 7, 101, 18]

LIS: [2, 3, 7, 101] → Length 4

Or: [2, 5, 7, 101] → Also length 4!

The DP Approach

For each number, ask: “What’s the longest increasing sequence ending at ME?”

def length_of_LIS(nums):
    if not nums:
        return 0

    n = len(nums)
    # dp[i] = longest ending at index i
    dp = [1] * n  # Minimum is 1 (just itself)

    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Walk-Through

nums = [10, 9, 2, 5, 3, 7]

i=0: dp = [1, 1, 1, 1, 1, 1]
     10 stands alone

i=1: 9 < 10? No.
     dp = [1, 1, 1, 1, 1, 1]

i=2: 2 < 10? No. 2 < 9? No.
     dp = [1, 1, 1, 1, 1, 1]

i=3: 5 > 10? No. 5 > 9? No. 5 > 2? YES!
     dp[3] = dp[2] + 1 = 2
     dp = [1, 1, 1, 2, 1, 1]

i=4: 3 > 2? YES!
     dp[4] = dp[2] + 1 = 2
     dp = [1, 1, 1, 2, 2, 1]

i=5: 7 > 5? YES! dp[5] = dp[3] + 1 = 3
     7 > 3? YES! dp[5] = max(3, dp[4]+1) = 3
     dp = [1, 1, 1, 2, 2, 3]

Answer: max(dp) = 3
LIS could be [2, 5, 7] or [2, 3, 7]

Time & Space

• Time: O(n²) - can be O(n log n) with binary search
• Space: O(n)

🪞 4. Longest Palindromic Subsequence (LPS)

The Mission

Find the longest sequence of letters that reads the same forwards and backwards.

What’s a Palindrome?

"racecar" → same forwards and backwards ✅
"hello"   → "olleh" backwards ≠ "hello" ❌

The Clever Trick

LPS of string S = LCS of S and reverse(S)

Why? A palindrome is the same as its reverse!

def longest_palindrome_subseq(s):
    # LPS = LCS of s and reverse of s
    return longest_common_subseq(s, s[::-1])

Or we can solve it directly:

Direct DP Solution

def longest_palindrome_subseq(s):
    n = len(s)
    # dp[i][j] = LPS in s[i:j+1]
    dp = [[0] * n for _ in range(n)]

    # Every single letter is a palindrome
    for i in range(n):
        dp[i][i] = 1

    # Check substrings of length 2 to n
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1

            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] + 2
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])

    return dp[0][n-1]

Visual Example

s = "bbbab"

     b   b   b   a   b
  b [1] [2] [3] [3] [4]
  b     [1] [2] [2] [3]
  b         [1] [1] [2]
  a             [1] [1]
  b                 [1]

Answer: dp[0][4] = 4
LPS = "bbbb"

The Rule

graph TD
    A["s i and s j"] --> B{Same letter?}
    B -->|Yes| C["2 + middle part"]
    B -->|No| D["max of skip left or skip right"]

Time & Space

• Time: O(n²)
• Space: O(n²)

🎯 Quick Comparison

🚀 Pro Tips

1. Is Subsequence → Use two pointers (fastest!)
2. LCS → Build 2D table, compare endings
3. LIS → Each position: what’s best ending at me?
4. LPS → It’s just LCS(s, reverse(s))!

🎮 Remember This!

Subsequences are about ORDER, not POSITION.

You’re picking items from a line without rearranging them.

The DP table asks: “What’s the best answer for this smaller problem?”

Build up from small answers to find the big answer!

🏁 You Did It!

You now understand the four key subsequence problems:

1. ✅ Is Subsequence - Two-pointer matching
2. ✅ LCS - Longest shared pattern in two strings
3. ✅ LIS - Longest growing sequence in numbers
4. ✅ LPS - Longest mirror pattern in one string

Each problem builds on the same core idea: breaking big problems into smaller ones and remembering the answers!