The O(n) Club: Implement strStr and Dodge That Haystack Hangover

The O(n) Club: Implement strStr and Dodge That Haystack Hangover

⚡ TL;DR

You want to find the first spot where ‘needle’ appears in your ‘haystack’. If the ‘needle’ is an empty string? Return 0, bask in the glory of passing test cases, and move on. Here’s brute force, manager-approved:

// Brute-force Java solution
public int strStr(String haystack, String needle) {
    if (needle.isEmpty()) return 0;
    for (int i = 0; i <= haystack.length() - needle.length(); i++) {
        if (haystack.substring(i, i + needle.length()).equals(needle)) {
            return i;
        }
    }
    return -1;
}

🧠 How Devs Usually Mess This Up

Let’s face it — this is a classic trap. Maybe you forget what to return when ‘needle’ is empty (spoiler: not -1!), or your loop comparison ends up as an off-by-one disaster that blows up at runtime. Or maybe you overcomplicate things like it’s a Saturday night refactor fest and start writing regexes for no reason. The real fail? Not returning 0 when ‘needle’ is an empty string. That’s basically a free interview pass that most people drop on the floor.

🔍 What’s Actually Going On

Think of your job as sliding a little window (the size of the ‘needle’) across a very tired conveyor belt (‘haystack’). Peek through the window: does the text match the ‘needle’? Nope? Slide one to the right and repeat. It’s not fancy, but it’s the workhorse of substring search—good enough unless you’re about to DNA-sequence the national archives. For big data, KMP might help, but if you’re pulling that out in round one, expect eye-rolls from the interviewer (and a follow-up about “space complexity” just for fun).

🛠️ PseudoCode

• If needle is empty:
  Return 0. You’ve basically already found it by looking at nothing.
• Slide window over haystack:
  Loop: i = 0 to haystack.length() - needle.length()
• Compare current window:
  If haystack.substring(i, i + needle.length()) equals needle, congrats, you win!
• Return index:
  Return i where the match happened.
• If nothing ever matches:
  After loop, return -1; someone hid your needle.

💻 The Code

// Java brute-force (the LeetCode special)
public int strStr(String haystack, String needle) {
    if (needle == null || haystack == null) return -1; // Defensive, not always needed
    if (needle.isEmpty()) return 0;
    int n = haystack.length(), m = needle.length();
    for (int i = 0; i <= n - m; i++) {
        if (haystack.substring(i, i + m).equals(needle)) {
            return i;
        }
    }
    return -1;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Empty needle? Return 0, not -1. You’ll fail test case 1 if you forget this. Guess how many people do?
• Needle longer than haystack? Don’t panic. Your loop won’t run and you’ll return -1. Computers: still pretty logical.
• Showoff warning: Java has indexOf() already. Unless you want to explain substring search algorithms to your grandma, just use it (unless interviewer says no).
• Performance: Brute-force: O((n-m+1) * m). Space: O(1). KMP: O(n + m), but unless you’re searching “War and Peace” for the word “war”, brute force rules.
• Case sensitivity: ‘A’ is not ‘a’, this isn’t kindergarten.

🧠 Interviewer Brain-Tattoo

“Return 0 for empty needles. Real devs dodge drama (and off-by-one bugs).”