Skip to main content

28. Find the Index of the First Occurrence in a String

easyAsked at Snap

Snap's chat search highlights the first match of a keyword in a message thread — this is the substring-search primitive behind that feature.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

  • 1 <= haystack.length, needle.length <= 10^4
  • haystack and needle consist of only lowercase English letters

Examples

Example 1

Input
haystack = "sadbutsad", needle = "sad"
Output
0

Example 2

Input
haystack = "leetcode", needle = "leeto"
Output
-1

Approaches

1. Sliding window brute force

For each starting index in haystack, compare the next needle.length characters. O(n*m) worst case but simple and correct.

Time
O(n*m)
Space
O(1)
function strStr(haystack, needle) {
  const n = haystack.length, m = needle.length;
  for (let i = 0; i <= n - m; i++) {
    let j = 0;
    while (j < m && haystack[i + j] === needle[j]) j++;
    if (j === m) return i;
  }
  return -1;
}

Tradeoff:

2. KMP (Knuth-Morris-Pratt)

Precompute a failure function (LPS array) for needle in O(m), then search haystack in O(n) without backtracking. The LPS array encodes the longest proper prefix of needle[0..i] that is also a suffix — letting the search skip re-comparisons.

Time
O(n + m)
Space
O(m)
function strStr(haystack, needle) {
  const n = haystack.length, m = needle.length;
  if (m === 0) return 0;
  // Build LPS (longest proper prefix which is also suffix)
  const lps = new Array(m).fill(0);
  let len = 0, i = 1;
  while (i < m) {
    if (needle[i] === needle[len]) {
      lps[i++] = ++len;
    } else if (len > 0) {
      len = lps[len - 1];
    } else {
      lps[i++] = 0;
    }
  }
  // Search
  let j = 0;
  i = 0;
  while (i < n) {
    if (haystack[i] === needle[j]) {
      i++; j++;
    }
    if (j === m) return i - j;
    if (i < n && haystack[i] !== needle[j]) {
      j > 0 ? (j = lps[j - 1]) : i++;
    }
  }
  return -1;
}

Tradeoff:

Snap-specific tips

Snap's chat search team cares about latency at scale — O(n*m) is fine for short messages but breaks on large conversation exports. Mentioning KMP or Rabin-Karp (rolling hash) and knowing which to choose based on needle length signals depth.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Find the Index of the First Occurrence in a String and other Snap interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →