Check substring search and algorithm optimization
Filed under Expedia
Free read 1 of 3Discuss what should be returned if the needle is empty (typically 0) and confirm constraints on string lengths.
The question
Given two strings `needle` and `haystack`, return the index of the first occurrence of `needle` in `haystack`, or -1 if `needle` is not part of `haystack`. Discuss brute force and optimized algorithms like KMP.
Constraints
- 1 <= haystack.length, needle.length <= 10^4
- haystack and needle consist of lowercase English characters.
Examples
- Input
- haystack = "sadbutsad", needle = "sad"
- Output
- 0
- Why
- "sad" occurs at index 0 and 6. The first occurrence is at index 0.
Approach
Discuss what should be returned if the needle is empty (typically 0) and confirm constraints on string lengths.
Iterate through each possible starting index in haystack and compare characters of the needle one by one. Time complexity is O(M * N) where M and N are lengths.
Discuss advanced pattern searching algorithms like Knuth-Morris-Pratt (KMP) or Rabin-Karp, which preprocess the needle to achieve O(M + N) time complexity by avoiding redundant comparisons.
Needle longer than haystack, identical strings, and strings with no matching characters.
Solution
O(N * M) time, O(1) space
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if not needle: return 0
n, m = len(haystack), len(needle)
for i in range(n - m + 1):
if haystack[i:i+m] == needle:
return i
return -1
Tips
- What they are testing: Test edge cases where the needle is longer than the haystack, or appears at the very end.
- Common mistake: Off-by-one errors in loop boundary conditions when checking substring windows.
Related Expedia questions
Collected from public candidate posts and coding forums. Updated Nov 2026.