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
andneedle
, return the index of the first occurrence ofneedle
inhaystack
, or-1
if it is not part ofhaystack
."
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 overhaystack
Use an inner loop (
j
) to check ifneedle[j] == haystack[i + j]
If
j
reachesneedle.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 comparisonsIf 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!
Subscribe to my newsletter
Read articles from Sujay P V directly inside your inbox. Subscribe to the newsletter, and don't miss out.
Written by
