28. Find the Index of the First Occurrence in a String (Easy)

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.

Example

• haystack = "sadbutsad", needle = "sad" → 0
• haystack = "leetcode", needle = "leeto" → -1
• haystack = "hello", needle = "ll" → 2

LeetCode 28 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force sliding window

Slide a window of length len(needle) one character at a time over haystack. At each position, compare the window against needle. Return the first position where they match.

Python

def str_str(haystack: str, needle: str) -> int:
    n, m = len(haystack), len(needle)    # L1: O(1)
    for i in range(n - m + 1):          # L2: loop, n-m+1 iterations
        if haystack[i:i + m] == needle:  # L3: slice + compare, O(m) each
            return i                     # L4: O(1) return
    return -1                            # L5: O(1)

TypeScript

function strStr(haystack: string, needle: string): number {
    const n = haystack.length, m = needle.length;   // L1: O(1)
    for (let i = 0; i <= n - m; i++) {              // L2: loop, n-m+1 iterations
        if (haystack.slice(i, i + m) === needle) {  // L3: slice + compare, O(m) each
            return i;                               // L4: O(1) return
        }
    }
    return -1;                                      // L5: O(1)
}

Go

func strStr(haystack string, needle string) int {
  n, m := len(haystack), len(needle)      // L1: O(1)
  for i := 0; i <= n-m; i++ {            // L2: loop, n-m+1 iterations
    if haystack[i:i+m] == needle {      // L3: slice + compare, O(m) each
      return i                        // L4: O(1) return
    }
  }
  return -1                               // L5: O(1)
}

Swift

final class Solution {
    func strStr(_ haystack: String, _ needle: String) -> Int {
        let text = Array(haystack), pattern = Array(needle)
        guard pattern.count <= text.count else { return -1 }
        for start in 0...(text.count - pattern.count) {
            var matches = true
            for offset in pattern.indices where text[start + offset] != pattern[offset] {
                matches = false
                break
            }
            if matches { return start }
        }
        return -1
    }
}

Where the time goes, line by line

Variables: n = len(haystack), m = len(needle).

Line	Per-call cost	Times executed	Contribution
L1 (lengths)	$O(1)$	1	$O(1)$
L2 (loop)	$O(1)$	n - m + 1	$O(n)$
L3 (slice + compare)	$O(m)$	up to n - m + 1	$O(n * m)$
L4 (return)	$O(1)$	1	$O(1)$
L5 (return -1)	$O(1)$	1	$O(1)$

The slice haystack[i:i+m] allocates a new string of length m and the == comparison scans up to m characters. Done at each of the ~n positions, that is $O(n * m)$ total.

Complexity

• Time: $O(n * m)$, driven by L3 (window comparison at every position).
• Space: $O(m)$ for the slice allocated at each step.

Approach 2: Built-in (interview-acceptable)

Python’s str.find() and JavaScript’s String.prototype.indexOf() use optimized algorithms under the hood. In an interview, returning the built-in result is explicitly acceptable for this problem.

Python

def str_str(haystack: str, needle: str) -> int:
    return haystack.find(needle)

TypeScript

function strStr(haystack: string, needle: string): number {
    return haystack.indexOf(needle);
}

Go

func strStr(haystack string, needle string) int {
  return strings.Index(haystack, needle)
}

Swift

final class Solution {
    func strStr(_ haystack: String, _ needle: String) -> Int {
        let text = Array(haystack), pattern = Array(needle)
        guard let range = text.firstRange(of: pattern) else { return -1 }
        return range.lowerBound
    }
}

This is $O(n)$ in the average case and $O(n * m)$ in the worst case, but the constant factor is far lower than a hand-rolled loop because the inner comparison runs in native code.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Note on KMP

The Knuth-Morris-Pratt algorithm solves this in $O(n + m)$ time and $O(m)$ space by precomputing a failure function over needle that allows the search to skip redundant comparisons. See KMP for the full walkthrough.

Summary

Approach	Time	Space
Brute sliding window	$O(n * m)$	$O(m)$
Built-in	$O(n)$ avg	$O(1)$
KMP	$O(n + m)$	$O(m)$

The brute approach is the clearest to reason about and fine for small inputs. Use the built-in in interviews unless the interviewer specifically asks for the algorithm. KMP is the canonical $O(n)$ solution.

Test cases

Python

# Quick smoke tests, paste into a REPL or save as test_028.py and run.
# Uses the brute sliding window implementation.

def str_str(haystack: str, needle: str) -> int:
    n, m = len(haystack), len(needle)
    for i in range(n - m + 1):
        if haystack[i:i + m] == needle:
            return i
    return -1

def _run_tests():
    assert str_str("sadbutsad", "sad") == 0
    assert str_str("leetcode", "leeto") == -1
    assert str_str("hello", "ll") == 2
    assert str_str("a", "a") == 0
    assert str_str("mississippi", "issip") == 4
    assert str_str("abc", "") == 0       # empty needle
    assert str_str("", "a") == -1        # empty haystack
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function strStr(haystack: string, needle: string): number {
    const n = haystack.length, m = needle.length;
    for (let i = 0; i <= n - m; i++) {
        if (haystack.slice(i, i + m) === needle) return i;
    }
    return -1;
}

console.assert(strStr("sadbutsad", "sad") === 0);
console.assert(strStr("leetcode", "leeto") === -1);
console.assert(strStr("hello", "ll") === 2);
console.assert(strStr("a", "a") === 0);
console.assert(strStr("mississippi", "issip") === 4);
console.assert(strStr("abc", "") === 0);
console.assert(strStr("", "a") === -1);
console.log("all tests pass");

Go

func strStr(haystack string, needle string) int {
  n, m := len(haystack), len(needle)
  for i := 0; i <= n-m; i++ {
    if haystack[i:i+m] == needle {
      return i
    }
  }
  return -1
}

Related topics

• KMP algorithm, the $O(n + m)$ solution to this exact problem
• Permutation in String, fixed-size sliding window on strings
• Longest Substring Without Repeating Characters, variable sliding window

Related concepts

• Array Scans, the linear pass habit of carrying just enough state while reading each item once.
• Two Pointers, the two index invariant that shrinks or coordinates positions without nested loops.