The O(n) Club: Is Subsequence: Why Order Matters (and Coffee Helps)

The O(n) Club: Is Subsequence — Why Order Matters (and Coffee Helps)

⚡ TL;DR

Checking if s is a subsequence of t? Don’t waste your time (or caffeine) generating every possible subsequence. Just point at things—literally. Use two pointers. Behold Java minimalism:

// Brute, but crystal clear. Please don’t interview with this!
public boolean isSubsequence(String s, String t) {
    int sIdx = 0;
    for (int tIdx = 0; tIdx < t.length() && sIdx < s.length(); tIdx++) {
        if (s.charAt(sIdx) == t.charAt(tIdx)) sIdx++;
    }
    return sIdx == s.length();
}

🧠 How Devs Usually Mess This Up

If we got a free drink every time someone confused subsequence and substring, Starbucks would be out of beans. Common blunders:

• Subsequence != Substring: “ace” can be a subsequence of “abcde”, but unless it’s all together (it’s not), it’s NOT a substring.
• The All-You-Can-Skip Buffet: You can skip as many characters in t as your heart desires, as long as the order of s is preserved. No shuffling. This isn’t a playlist.
• The Brute Force Party: Generating all of t’s subsequences is like buying tickets for every possible bus route—sure, you’ll get there eventually, but why are you doing this to yourself?

🔍 What’s Actually Going On

It’s like a chef taste-testing soup, looking for just the right ingredients (in the correct order): Tip the ladle into the ‘t’ pot, peeking for “s” flavors. For each matching taste, chop-chop: advance the ‘s’ index. If the chef’s list (s) empties before the soup runs out (t), congrats—you’ve recreated grandma’s subsequence recipe. If not, dinner’s off.

🛠️ PseudoCode

• Start with both indices at zero.

  int sIdx = 0, tIdx = 0;

  (Two pointers—classic dev move.)
• While you haven’t reached the end of either string:
  • If s.charAt(sIdx) == t.charAt(tIdx), move sIdx (found another match!).
  • Always move tIdx (because ‘t’ keeps coming at you, relentless like the build queue).
• If sIdx == s.length(), return true (you matched every ingredient).
• If t ends first, too bad—return false.

💻 The Code

// Sleek, Java-approved:
public boolean isSubsequence(String s, String t) {
    if (s.length() == 0) return true; // Empty s? Always a subsequence!
    int sIdx = 0, tIdx = 0;
    while (tIdx < t.length() && sIdx < s.length()) {
        if (s.charAt(sIdx) == t.charAt(tIdx)) {
            sIdx++;
        }
        tIdx++;
    }
    return sIdx == s.length();
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Empty Strings: If s is empty, it’s always a subsequence. Like sneaking into a movie: there’s nothing to check.
• Out-of-Bounds: If t is empty and s isn’t, you’ll end up hungry (false).
• Substring Fakeouts: Don’t use t.contains(s); we need order, not adjacency.
• Performance: O(N) time, O(1) space. The algorithm’s as lightweight as your hope when you hit ‘Submit’ on LeetCode.
• Trick Interview Variant: If you had to test a billion s-strings against the same t, you’d want some pre-processing (hello, binary search over character indices!). But for one pair? Two pointers, period.

🧠 Interviewer Brain-Tattoo

“Subsequence: in order, out of sight. Substring: in order, shoulder-to-shoulder. Don’t mix ‘em, or the interviewer will mix you.”