Find the Index of the First Occurrence in a String

Easy#28fixed size

You get two strings, a long haystack and a short needle. Return the index where the needle first appears in the haystack, or -1 if it never does. Our example: "bad" in "ecbbadfg" — the answer is 3.

28 Find the Index of the First Occurrence in a StringWalkthrough · 1×

Example: haystack = "ecbbadfg", needle = "bad". Each letter has a code, a = 1, b = 2, …; the window keeps the sum of its codes.

0e1c2b3b4a5d6f7g53221467needlebadsum–target–
not reached yetwindowletter coming inletter going out, a false alarmleft the windowthe needle

The needle has 3 letters: every window is 3 letters long

01/35
restart · back · play · step
Speed
1function strStr(haystack, needle):
2 m = len(needle)
3 target = sum of code(c) for c in needle // a = 1, …
4 sum = 0
5 for right from 0 to len(haystack) - 1:
6 sum = sum + code(haystack[right])
7 if right >= m:
8 sum = sum - code(haystack[right - m])
9 if right >= m - 1 and sum == target:
10 start = right - m + 1
11 if haystack[start .. right] == needle:
12 return start
13 return -1
state
m
3
target
–
sum
–
right
–
start
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The window is always as long as the needle and moves one letter at a time, so every place the needle could start is checked, the first one first.
  2. If the sums differ, the letters differ: such a window is skipped in O(1). The sum is updated like a running sum, one code in and one out.
  3. Equal sums do not mean equal letters ("cbb" and "bad" both make 7), so a window with the right sum is still compared letter by letter.

Complexity

Time: the sums take O(n + m), plus O(m) for each window whose sum matches. With few false alarms that is O(n + m); in the worst case, when nearly every window has the right sum, O(n · m). Memory O(1).

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.