The O(n) Club: Distinct Subsequences, or How to Skip Letters Like a Pro (and Keep Your Sanity)

The O(n) Club: Distinct Subsequences, or How to Skip Letters Like a Pro (and Keep Your Sanity)

⚡ TL;DR

Want the number of ways to get t as a subsequence of s—skipping letters, keeping order, while retaining your (last thread of) sanity? Here’s the basic (and eye-wateringly inefficient) brute-force Java:

// Don't use this in production (or interviews)
int count(String s, String t, int i, int j) {
    if (j == t.length()) return 1;
    if (i == s.length()) return 0;
    int skip = count(s, t, i + 1, j);
    int use = s.charAt(i) == t.charAt(j) ? count(s, t, i + 1, j + 1) : 0;
    return skip + use;
}

🧠 How Devs Usually Mess This Up

Classic dev missteps include:

• Brute Force Recursion: More like brute force nap time—hello, stack overflow!
• Substring Substitution: If you’re checking for substrings, you’re solving a different (and much easier) problem altogether.
• DP Init Carnage: Everyone breaks the base cases at least once. Forgetting dp[0] = 1 makes the answer perpetually zero unless the universe is empty.

🔍 What’s Actually Going On

Think of building “BAT” out of “BEAUTIFUL ATTRACTIVE TUBAS” by skipping everything except the letters you need (and not mixing them up). Dynamic programming’s inner chef says at each letter: ‘Should I use this to match my next target, or should I toss it in the compost bin and move on?’

The magic is in keeping order, not worrying about gaps—the pattern is everything. This isn’t substring karaoke; it’s string jazz improvisation.

🛠️ PseudoCode

• Set up: Create an array dp of t.length + 1, with dp[0] = 1 (empty t lives everywhere).
• For every letter in s (left to right):
  • Go backwards through t (so important things aren’t overwritten by overeager Java loops).
  • If s.charAt(i - 1) == t.charAt(j - 1), then dp[j] += dp[j - 1] (take it or leave it—both count).
  • (Otherwise, skip—they already carried forward the ways to reach j.)
• Answer? dp[t.length] (your unique O(n) club badge).

// 1D DP pseudo-Java
int[] dp = new int[t.length() + 1];
dp[0] = 1;
for (int i = 1; i <= s.length(); i++) {
    for (int j = t.length(); j >= 1; j--) {
        if (s.charAt(i-1) == t.charAt(j-1)) {
            dp[j] += dp[j-1];
        }
    }
}
return dp[t.length];

💻 The Code

public int numDistinct(String s, String t) {
    int m = s.length(), n = t.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = n; j >= 1; j--) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) {
                dp[j] += dp[j - 1];
            }
        }
    }
    return dp[n];
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Target longer than source? Just return 0 and avoid existential dread.
• Off-by-one Indexing: Java: zero-based. Your patience: about to be negative one. Watch those i-1 and j-1.
• Forget dp[0] = 1? You’ll get zero every time. Every. Single. Time.
• Time/Space Complexity: Time: O(mn)—space: O(n)—tolerable unless s is all of Wikipedia.
• Overflow? Test huge cases; if you see negative numbers, use longs or call for help.

🧠 Interviewer Brain-Tattoo

“Whenever the interviewer says, ‘How many paths/ways…’, somewhere, a dynamic programming table feels a chill.”