Subsequence DP

Subsequence DP: Finding Hidden Patterns in Sequences

The Treasure Hunt Analogy

Imagine you have a long string of beads on a necklace. Some beads are red, some blue, some green. Now, your friend gives you another necklace and asks: “What’s the longest matching pattern we can find in both?”

You can’t change the order of beads. You can only pick certain beads while keeping their order. That’s what a subsequence is!

What is a Subsequence?

Think of it like this:

Original word: “ABCDE” Subsequence: “ACE” (we picked A, skipped B, picked C, skipped D, picked E)

Key Rule: Keep the order. Never swap positions!

A B C D E
↓   ↓   ↓
A   C   E  ← Valid subsequence!

1. Is Subsequence (The Easiest Check)

The Story

You’re a detective. Someone claims that the word “ace” is hiding inside “abcde”. Your job? Find each letter in order.

How It Works

// Is "ace" a subsequence of "abcde"?
boolean isSubsequence(String s, String t) {
    int i = 0;  // pointer for s
    for (char c : t.toCharArray()) {
        if (i < s.length() && c == s.charAt(i)) {
            i++;  // Found a match!
        }
    }
    return i == s.length();
}

Visual Example

t: a b c d e
   ↓   ↓   ↓
s: a   c   e  → Found all 3! Return TRUE

Time: O(n) - One pass through the string Space: O(1) - Just two pointers

2. Longest Common Subsequence (LCS)

The Story

Two siblings have different favorite words: “ABCBDAB” and “BDCABA”. They want to find the longest matching pattern in both!

The Magic Table

We build a grid. Each cell asks: “What’s the longest match so far?”

    ""  B  D  C  A  B  A
""   0  0  0  0  0  0  0
A    0  0  0  0  1  1  1
B    0  1  1  1  1  2  2
C    0  1  1  2  2  2  2
B    0  1  1  2  2  3  3
D    0  1  2  2  2  3  3
A    0  1  2  2  3  3  4
B    0  1  2  2  3  4  4

The Rules

graph TD
    A["Compare two characters"] --> B{Do they match?}
    B -->|Yes| C["Add 1 to diagonal"]
    B -->|No| D["Take max of left/top"]

Java Code

int lcs(String s1, String s2) {
    int m = s1.length();
    int n = s2.length();
    int[][] dp = new int[m + 1][n + 1];

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i-1) == s2.charAt(j-1)) {
                dp[i][j] = dp[i-1][j-1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i-1][j],
                                    dp[i][j-1]);
            }
        }
    }
    return dp[m][n];
}

Answer: The LCS is “BCBA” with length 4

3. Longest Increasing Subsequence (LIS)

The Story

You’re stacking blocks! Each new block must be taller than the last. Given blocks of heights [10, 9, 2, 5, 3, 7, 101, 18], what’s the tallest tower you can build?

Visual Journey

Heights: 10  9  2  5  3  7  101  18
              ↓  ↓     ↓   ↓
Stack:        2  5     7  101  → Length 4!

Or:           2  3     7   18  → Also 4!

The DP Approach

Each position stores: “What’s the longest increasing chain ending here?”

Array:  [10, 9, 2, 5, 3, 7, 101, 18]
DP:     [ 1, 1, 1, 2, 2, 3,   4,  4]

Java Code

int lis(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
    return Arrays.stream(dp).max().getAsInt();
}

Time: O(n²) Pro Tip: Can be optimized to O(n log n) with binary search!

4. Longest Palindromic Subsequence (LPS)

The Story

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

The Trick

LPS of a string = LCS of the string and its reverse!

Original: "bbbab"
Reverse:  "babbb"
LCS:      "bbbb"  → Length 4!

Why This Works

graph TD
    A["String: bbbab"] --> B["Reverse: babbb"]
    B --> C["Find LCS"]
    C --> D["LCS = bbbb"]
    D --> E["Longest Palindrome!"]

Java Code

int lps(String s) {
    String rev = new StringBuilder(s)
                    .reverse().toString();
    return lcs(s, rev);  // Reuse LCS!
}

// Or direct DP approach:
int lpsDirect(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];

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

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j)) {
                dp[i][j] = dp[i+1][j-1] + 2;
            } else {
                dp[i][j] = Math.max(dp[i+1][j],
                                    dp[i][j-1]);
            }
        }
    }
    return dp[0][n-1];
}

The Pattern Summary

All four problems share one secret:

graph TD
    A["Subsequence DP"] --> B["Build a table"]
    B --> C["Compare characters"]
    C --> D{Match?}
    D -->|Yes| E["Extend from diagonal"]
    D -->|No| F["Take best from neighbors"]

Quick Reference

Real-World Uses

• Git Diff: Finds longest matching lines between file versions
• DNA Analysis: Compares gene sequences
• Spell Check: Suggests similar words
• Video Streaming: Compresses frame differences

Remember This!

1. Subsequence = Pick elements, keep order
2. LCS = Match two sequences, build 2D grid
3. LIS = Stack increasing numbers, look backwards
4. LPS = Reverse trick or diagonal DP

You now have the treasure map to solve any subsequence problem!