Skip to main content

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

easyAsked at Bloomberg

Implement strStr() — return the index of the first occurrence of needle in haystack, or -1. Bloomberg uses this as the gateway to substring algorithms: brute force is fine for warm-up, but they always probe for KMP if the conversation goes deeper.

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

Source citations

Public interview reports confirming this problem appears in Bloomberg loops.

  • Glassdoor (2026-Q1)— Bloomberg SWE phone-screen reports cite strStr() as a string-matching warm-up.
  • Blind (2025-11)— Bloomberg new-grad reports note the KMP follow-up as a common interview probe.

Problem

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.

Constraints

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

Examples

Example 1

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

Explanation: "sad" occurs at index 0 and 6. The first occurrence is at index 0, so we return 0.

Example 2

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

Explanation: "leeto" did not occur in "leetcode".

Approaches

1. Brute-force sliding window

Try every starting index in haystack; compare needle char-by-char.

Time
O(n * m)
Space
O(1)
function strStr(haystack, needle) {
  const n = haystack.length;
  const m = needle.length;
  if (m === 0) return 0;
  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: Within constraints (10^4 each), n * m = 10^8 — borderline but passes. Bloomberg interviewers accept this for the warm-up; expect a follow-up for KMP.

2. KMP (Knuth-Morris-Pratt) for the follow-up

Build a longest-prefix-suffix table for needle, then walk haystack without backtracking.

Time
O(n + m)
Space
O(m)
function strStrKMP(haystack, needle) {
  if (needle.length === 0) return 0;
  const lps = new Array(needle.length).fill(0);
  let len = 0;
  for (let i = 1; i < needle.length;) {
    if (needle[i] === needle[len]) { lps[i++] = ++len; }
    else if (len) { len = lps[len - 1]; }
    else { lps[i++] = 0; }
  }
  let i = 0, j = 0;
  while (i < haystack.length) {
    if (haystack[i] === needle[j]) { i++; j++; }
    if (j === needle.length) return i - j;
    else if (i < haystack.length && haystack[i] !== needle[j]) {
      if (j) j = lps[j - 1];
      else i++;
    }
  }
  return -1;
}

Tradeoff: Optimal O(n + m). Bloomberg interviewers don't always require this; mention it as 'if we needed faster I'd use KMP' and only code it if probed.

Bloomberg-specific tips

Bloomberg interviewers grade on the TRADEOFF NARRATION. Lead with brute force, name the complexity, then say 'if n and m were larger I'd use KMP for O(n+m).' Volunteering KMP without writing it shows breadth without burning interview time.

Common mistakes

  • Off-by-one in the outer loop: i must reach n - m, NOT n - m - 1.
  • Returning the wrong index (e.g., the end of match instead of start).
  • Forgetting to handle the empty-needle case (return 0).

Follow-up questions

An interviewer at Bloomberg may pivot to one of these next:

  • Repeated Substring Pattern (LC 459) — KMP failure-table application.
  • Shortest Palindrome (LC 214) — clever KMP trick.
  • Longest Happy Prefix (LC 1392) — KMP table directly.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Will Bloomberg actually ask KMP on the board?

Rarely. Most candidates pass with the brute-force + a verbal acknowledgement that KMP exists. Still worth memorizing once.

Is using haystack.indexOf(needle) acceptable?

Only as a sanity baseline; the interviewer will ask you to implement it from scratch. Mention indexOf to show you know the language, then code the loop.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →