Subsequence DP

🧩 Subsequence DP: Finding Patterns in Sequences

The Treasure Hunt Analogy

Imagine you have a treasure map with clues scattered along a path. You can skip some clues, but you can’t go backwards. Your goal? Find the best collection of clues that leads to treasure!

That’s exactly what Subsequence DP does with strings and arrays. We look for patterns by picking elements in order (but not necessarily next to each other).

🎯 What is a Subsequence?

A subsequence is like picking cards from a deck without shuffling:

• You can skip cards
• You must keep the order
• You can’t rearrange

Example:

String: "ABCDE"

Valid subsequences:
✅ "ACE" (skip B, D)
✅ "BD" (skip A, C, E)
✅ "ABCDE" (take all)
✅ "" (take none)

Invalid:
❌ "ECA" (wrong order!)

🔗 Longest Common Subsequence (LCS)

The Story

Two friends wrote down their favorite movies. They want to find the longest list of movies they both like in the same order.

Friend 1: "ABCDGH"
Friend 2: "AEDFHR"

LCS: "ADH" (length 3)

Both have A, then D, then H — in that order!

How It Works

We build a grid comparing both strings:

graph TD
    A["Compare each character"] --> B{Same character?}
    B -->|Yes| C["Take it + add 1"]
    B -->|No| D["Pick best from left or top"]
    C --> E["Move diagonally"]
    D --> E

The Code

function longestCommonSubsequence(text1, text2) {
  const m = text1.length;
  const n = text2.length;

  // Create grid filled with zeros
  const dp = Array(m + 1).fill(null)
    .map(() => Array(n + 1).fill(0));

  // Fill the grid
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (text1[i-1] === text2[j-1]) {
        // Characters match! Diagonal + 1
        dp[i][j] = dp[i-1][j-1] + 1;
      } else {
        // No match: best of left or top
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
      }
    }
  }

  return dp[m][n];
}

Visual Example

For strings “ACE” and “BCE”:

Answer: 2 (subsequence “CE”)

Key Insight 💡

When characters match, we “lock in” that match and look diagonally back. When they don’t, we take the best we found so far.

📈 Longest Increasing Subsequence (LIS)

The Story

You’re climbing a mountain staircase. Each step has a number. You want to find the longest path where each step is higher than the last.

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

LIS: [2, 3, 7, 18] or [2, 3, 7, 101]
Length: 4

How It Works

For each position, ask: “What’s the longest increasing path ending HERE?”

graph TD
    A["For each number"] --> B["Look at all previous numbers"]
    B --> C{Previous < Current?}
    C -->|Yes| D["Can extend that path!"]
    C -->|No| E["Skip it"]
    D --> F["Keep best extension + 1"]

The Code

function lengthOfLIS(nums) {
  if (nums.length === 0) return 0;

  // dp[i] = longest increasing ending at i
  const dp = new Array(nums.length).fill(1);

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      // Can we extend the sequence ending at j?
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
  }

  return Math.max(...dp);
}

Visual Example

Array: [3, 1, 4, 1, 5]

• dp[0] = 1 (just [3])
• dp[1] = 1 (just [1], can’t follow 3)
• dp[2] = 2 ([1,4] or [3,4])
• dp[3] = 1 (just [1])
• dp[4] = 3 ([1,4,5])

Answer: 3

Key Insight 💡

Every position starts at 1 (itself). Then we check all previous positions to find the best path we can extend.

🪞 Longest Palindromic Subsequence (LPS)

The Story

A palindrome reads the same forwards and backwards (like “racecar”). Given any string, find the longest subsequence that forms a palindrome.

String: "bbbab"
LPS: "bbbb" (length 4)

String: "cbbd"
LPS: "bb" (length 2)

The Magic Trick ✨

Here’s a secret: LPS = LCS of string with its reverse!

String: "AGBCBA"
Reverse: "ABCBGA"
LCS: "ABCBA" (length 5) ← That's palindromic!

The Code

function longestPalinSubseq(s) {
  const n = s.length;
  // dp[i][j] = LPS length from i to j
  const dp = Array(n).fill(null)
    .map(() => Array(n).fill(0));

  // Every single character is palindrome of 1
  for (let i = 0; i < n; i++) {
    dp[i][i] = 1;
  }

  // Check substrings of increasing length
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i <= n - len; i++) {
      const j = i + len - 1;

      if (s[i] === s[j]) {
        // Matching ends! Add 2 + middle
        dp[i][j] = dp[i+1][j-1] + 2;
      } else {
        // Take best of skipping left or right
        dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
      }
    }
  }

  return dp[0][n-1];
}

Visual Example

String: “bbbab”

We build a table where dp[i][j] = LPS from index i to j:

Answer: 4 (subsequence “bbbb”)

Key Insight 💡

If the ends match, they’re part of our palindrome! If not, try dropping one end.

✅ Is Subsequence

The Story

You have a shopping list (small string) and a huge catalog (big string). Can you find every item on your list, in order, within the catalog?

List (s): "abc"
Catalog (t): "ahbgdc"

Is "abc" a subsequence of "ahbgdc"?
✅ YES! (a...b...c)

How It Works

Use two pointers — one for each string:

graph TD
    A["Start both pointers at 0"] --> B{Characters match?}
    B -->|Yes| C["Move BOTH pointers"]
    B -->|No| D["Move catalog pointer only"]
    C --> E{List pointer done?}
    D --> E
    E -->|Yes| F["SUCCESS!"]
    E -->|No| G{Catalog exhausted?}
    G -->|Yes| H["FAIL"]
    G -->|No| B

The Code

function isSubsequence(s, t) {
  let sPointer = 0;
  let tPointer = 0;

  while (sPointer < s.length && tPointer < t.length) {
    // Found a match!
    if (s[sPointer] === t[tPointer]) {
      sPointer++;
    }
    // Always move through catalog
    tPointer++;
  }

  // Did we find all characters in s?
  return sPointer === s.length;
}

Visual Example

s = “ace”, t = “abcde”

t: a b c d e
   ↑
s: a c e
   ↑
Match 'a'! Move both.

t: a b c d e
     ↑
s: a c e
     ↑
'b' ≠ 'c'. Move t only.

t: a b c d e
       ↑
s: a c e
     ↑
Match 'c'! Move both.

t: a b c d e
         ↑
s: a c e
       ↑
'd' ≠ 'e'. Move t only.

t: a b c d e
           ↑
s: a c e
       ↑
Match 'e'! Move both.

s is exhausted → SUCCESS! ✅

Key Insight 💡

This is the simplest subsequence problem — just greedy matching. No DP table needed!

🧠 Pattern Summary

🎮 The Subsequence DP Mindset

When you see a subsequence problem, ask:

1. How many strings/arrays? (1 or 2)
2. What am I looking for? (longest, shortest, exists?)
3. What’s the condition? (matching, increasing, palindrome?)

Then pick your weapon:

• One string, check condition: LIS-style (1D DP)
• Two strings, find common: LCS-style (2D DP)
• Palindrome: Think about the reverse trick!
• Just checking existence: Try two pointers first

🚀 You’ve Got This!

Subsequence DP is all about building on what you’ve already found.

• Small problems → big solutions
• Overlapping subproblems → use a table
• Optimal substructure → each step is locally optimal

Keep practicing, and soon you’ll see subsequences everywhere! 🎯