Finding the First Occurrence of a String in Java — Two Pointers vs. Sliding Window

One of the most classic problems you'll encounter in string manipulation is this:

"Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if it is not part of haystack."

Avoiding the Brute Force Approach

At first, I considered the brute-force approach. But I quickly realized the time complexity would be too high—likely O(n * m)—and that might not pass efficiently on LeetCode. So I dropped that idea and looked for smarter options.

Two Approaches I Explored

1. Two Pointers

2. Sliding Window

Two Pointer Approach — Manual but Effective

Since I wasn't fully confident with the sliding window pattern yet, I started with the two pointer method.

Logic:

• Use an outer loop (i) to slide over haystack

• Use an inner loop (j) to check if needle[j] == haystack[i + j]

• If j reaches needle.length(), we found a full match

Java Code:

class Solution {
    public int strStr(String haystack, String needle) {
        for (int i = 0; i <= haystack.length() - needle.length(); i++) {
            int j = 0;
            while (j < needle.length() && haystack.charAt(i + j) == needle.charAt(j)) {
                j++;
            }
            if (j == needle.length()) {
                return i;
            }
        }
        return -1;
    }
}

Why This Works:

• We avoid out-of-bounds issues by limiting i

• We compare character-by-character

• This is similar to a brute-force match, but much more controlled

Sliding Window — Simple & Clean

Once I grasped the two pointer logic, I turned to the more elegant sliding window approach.

Logic:

• Create a window of size needle.length()

• Slide it over haystack using substring comparisons

• If the current window matches needle, return the start index

Java Code:

class Solution {
    public int strStr(String haystack, String needle) {
        int windowSize = needle.length();
        for (int i = 0; i <= haystack.length() - windowSize; i++) {
            String window = haystack.substring(i, i + windowSize);
            if (window.equals(needle)) {
                return i;
            }
        }
        return -1;
    }
}

Why This Feels Better:

• Cleaner syntax using substring

• Less manual character comparison

• Easy to read and debug

Performance Observations

Although both have O(n * m) worst-case time complexity:

• The sliding window version sometimes runs faster on LeetCode, likely because substring is optimized internally.

• The two-pointer approach avoids creating new strings, so it may use slightly less memory.

Real-world performance depends on Java's internal string handling and how the platform benchmarks it.

Final Thoughts

Both methods are valid, but if you're new to string problems:

• Start with the two-pointer method to understand how matching works

• Move to sliding window once you're comfortable—it’s elegant and concise

Got Thoughts?

Have you tried this problem using KMP or other advanced pattern matching algorithms? Let me know in the comments—I’d love to explore those next!