โ† Expedia questions

Check substring search and algorithm optimization

Filed under Expedia

Free read 1 of 3

Discuss 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

  1. Discuss what should be returned if the needle is empty (typically 0) and confirm constraints on string lengths.

Solution

O(N * M) time, O(1) space

Python
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.