Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Find the Index of the First Occurrence in a String solution and explanation

EasyStringString MatchingTwo Pointers6 min read47.0% acceptanceUpdated 9 Apr 2026
Asked atPocket GemsLg ElectronicsAmazonMicrosoftBloombergApple
+10 moreTCSExpediaQualcommCapgeminiGoogleMetaZohoInfosysPayPalLinkedIn
Practise Find the Index of the First Occurrence in a String
35:52
Knuth–Morris–Pratt KMP - Find the Index of the First Occurrence in a String - Leetcode 28 - PythonNeetCode · 35:52 · 195K viewsWatch on YouTube
9 more videos on this problem
  1. Knuth–Morris–Pratt KMP - Find the Index of the First Occurrence in a String - Leetcode 28 - PythonNeetCode · 35:52 · 195K views
  2. Find the Index of the First Occurrence in a String - Leetcode 28 - PythonNeetCode · 9:38 · 98K views
  3. Find the index of the first occurrence in a string | Leetcode 28Technosage · 6:43 · 92K views
  4. Find the Index of the First Occurrence in a String | Google, Microsoft | Leetcode 28codestorywithMIK · 15:32 · 22K views
  5. LeetCode 28: Find Index of First Occurrence in a String | KMP AlgorithmAbstracted Away · 13:32 · 20K views
  6. Find the index of the first occurrence in a string | Leetcode 28 | O(n) time ComplexityTechnosage · 4:36 · 10K views
  7. Find the Index of the First Occurrence in a String | Leetcode #28Techdose · 9:17 · 8K views
  8. 28. Find the Index of the First Occurrence in a String | Interview Preparation | English | code iocode io - English · 11:06 · 5K views
  9. Leetcode 28: Find the Index of First Occurrence in a String | Java SolutionMaybe Something New · 5:28 · 4K views
  10. 28. Find the Index of the First Occurrence in a String | JavaScript | LeetCode Daily ChallengeLeetCodeWithMonu · 13:42 · 2K views

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

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", so we return -1.

Constraints:

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

Approach overview

Problem Overview: Given two strings haystack and needle, return the index of the first occurrence of needle inside haystack. If the substring does not exist, return -1. The task is essentially substring search—scan a larger string and determine where a smaller pattern appears first.

Approach 1: Brute Force String Comparison (O(n * m) time, O(1) space)

The simplest strategy checks every possible starting position in haystack. For each index i, compare characters sequentially with needle. If all m characters match, return i. If a mismatch occurs, shift the starting point by one and try again. This approach performs at most n starting checks and up to m comparisons per check, leading to O(n * m) time complexity and constant space.

This method is easy to implement and often sufficient for small inputs. It also demonstrates a clear understanding of substring matching mechanics. The logic relies on sequential character comparison and basic iteration over a string. Some implementations optimize slightly using pointer movement similar to two pointers, but the worst‑case complexity remains quadratic.

Approach 2: KMP (Knuth–Morris–Pratt) Algorithm (O(n + m) time, O(m) space)

The KMP algorithm improves performance by avoiding repeated comparisons after a mismatch. Instead of restarting the match from the next index in haystack, KMP uses a preprocessing step on needle to build the LPS (Longest Prefix Suffix) array. The LPS array stores the length of the longest prefix that is also a suffix for every prefix of the pattern.

During scanning, if a mismatch occurs after matching several characters, the algorithm uses the LPS value to determine the next valid comparison position without rechecking characters already known to match. This reduces redundant comparisons and guarantees linear time complexity O(n + m). The additional array requires O(m) space.

KMP is a classic string matching algorithm and scales efficiently for long strings or repeated pattern structures. It’s commonly used in search engines, compilers, and text processing systems where substring search happens frequently.

Recommended for interviews: Start with the brute force explanation because it shows you understand the direct substring comparison process. Then discuss the inefficiency caused by repeated comparisons. Follow up with the KMP optimization, explaining how the LPS array prevents rechecking characters. Interviewers often expect awareness of KMP or similar linear string matching algorithms for this problem.

Approach 1: Brute Force Approach

The brute force approach involves iterating over each possible starting position of the needle in the haystack and checking if the substring from that position matches the needle.

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

print(strStr("sadbutsad", "sad")) # Output: 0
public class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();
        for (int i = 0; i <= m - n; i++) {
            int j = 0;
            for (; j < n; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j))
                    break;
            }
            if (j == n) return i;
        }
        return -1;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.strStr("sadbutsad", "sad")); // Output: 0
    }
}
#include <iostream>
using namespace std;
int strStr(string haystack, string needle) {
    int m = haystack.size();
    int n = needle.size();
    if (n == 0) return 0;
    for (int i = 0; i <= m - n; i++) {
        int j = 0;
        for (j = 0; j < n; j++) {
            if (haystack[i + j] != needle[j])
                break;
        }
        if (j == n) return i;
    }
    return -1;
}

int main() {
    cout << strStr("sadbutsad", "sad") << endl; // Output: 0
    return 0;
}
function strStr(haystack, needle) {
    let m = haystack.length;
    let n = needle.length;
    if (n === 0) return 0;
    for (let i = 0; i <= m - n; i++) {
        let j = 0;
        for (; j < n; j++) {
            if (haystack[i + j] !== needle[j])
                break;
        }
        if (j === n) return i;
    }
    return -1;
}

console.log(strStr("sadbutsad", "sad")); // Output: 0
#include <stdio.h>
#include <string.h>

int strStr(char * haystack, char * needle) {
    int m = strlen(haystack);
    int n = strlen(needle);
    if (n == 0) return 0;
    for (int i = 0; i <= m - n; i++) {
        int j;
        for (j = 0; j < n; j++) {
            if (haystack[i + j] != needle[j])
                break;
        }
        if (j == n) return i;
    }
    return -1;
}

int main() {
    char *haystack = "sadbutsad";
    char *needle = "sad";
    printf("%d\n", strStr(haystack, needle)); // Output: 0
    return 0;
}
public class Solution {
    public int StrStr(string haystack, string needle) {
        int m = haystack.Length;
        int n = needle.Length;
        if (n == 0) return 0;
        for (int i = 0; i <= m - n; i++) {
            int j = 0;
            for (; j < n; j++) {
                if (haystack[i + j] != needle[j])
                    break;
            }
            if (j == n) return i;
        }
        return -1;
    }
    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.StrStr("sadbutsad", "sad")); // Output: 0
    }
}

This Python solution uses slicing to compare parts of the haystack with the needle.

Complexity

Time Complexity: O((m-n+1)*n), where m is the length of haystack and n is the length of needle.
Space Complexity: O(1).

Try this approach in the editor

Approach 2: KMP Algorithm

The KMP (Knuth-Morris-Pratt) algorithm is a more efficient string-searching algorithm. It preprocesses the needle to create a longest prefix-suffix (LPS) array, which is used to skip unnecessary comparisons while searching in the haystack.

def strStr(haystack: str, needle: str) -> int:
    if not needle:
        return 0
    def computeLPS(pattern):
        lps = [0] * len(pattern)
        length = 0
        i = 1
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        return lps
    lps = computeLPS(needle)
    i = j = 0
    while i < len(haystack):
        if haystack[i] == needle[j]:
            i += 1
            j += 1
        if j == len(needle):
            return i - j
        elif i < len(haystack) and haystack[i] != needle[j]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return -1

print(strStr("sadbutsad", "sad")) # Output: 0
public class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();
        if (n == 0) return 0;
        int[] lps = new int[n];
        computeLPSArray(needle, n, lps);
        int i = 0, j = 0;
        while (i < m) {
            if (haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            }
            if (j == n) return i - j;
            else if (i < m && haystack.charAt(i) != needle.charAt(j)) {
                if (j != 0) j = lps[j - 1];
                else i++;
            }
        }
        return -1;
    }
    void computeLPSArray(String needle, int n, int[] lps) {
        int length = 0;
        lps[0] = 0;
        int i = 1;
        while (i < n) {
            if (needle.charAt(i) == needle.charAt(length)) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.strStr("sadbutsad", "sad")); // Output: 0
    }
}
#include <iostream>
#include <vector>
using namespace std;

void computeLPSArray(string pat, int M, int* lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int strStr(string txt, string pat) {
    int N = txt.size();
    int M = pat.size();
    int lps[M];
    computeLPSArray(pat, M, lps);
    int i = 0;
    int j = 0;
    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }
        if (j == M) {
            return i - j;
            j = lps[j - 1];
        } else if (i < N && pat[j] != txt[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
    return -1;
}

int main() {
    cout << strStr("sadbutsad", "sad") << endl; // Output: 0
    return 0;
}
function strStr(haystack, needle) {
    if (needle.length === 0) return 0;
    function computeLPSArray(pattern) {
        let lps = new Array(pattern.length).fill(0);
        let length = 0;
        let i = 1;
        while (i < pattern.length) {
            if (pattern[i] === pattern[length]) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length !== 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }
    let lps = computeLPSArray(needle);
    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 !== 0) j = lps[j - 1];
            else i++;
        }
    }
    return -1;
}

console.log(strStr("sadbutsad", "sad")); // Output: 0
#include <stdio.h>
#include <string.h>

void computeLPSArray(char* pat, int M, int* lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

int strStr(char* txt, char* pat) {
    int N = strlen(txt);
    int M = strlen(pat);
    int lps[M];
    computeLPSArray(pat, M, lps);
    int i = 0;
    int j = 0;
    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }
        if (j == M) {
            return i - j;
            j = lps[j - 1];
        } else if (i < N && pat[j] != txt[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i = i + 1;
        }
    }
    return -1;
}

int main() {
    char* haystack = "sadbutsad";
    char* needle = "sad";
    printf("%d\n", strStr(haystack, needle)); // Output: 0
    return 0;
}
public class Solution {
    public int StrStr(string haystack, string needle) {
        int m = haystack.Length;
        int n = needle.Length;
        if (n == 0) return 0;
        int[] lps = new int[n];
        computeLPSArray(needle, n, lps);
        int i = 0, j = 0;
        while (i < m) {
            if (haystack[i] == needle[j]) {
                i++;
                j++;
            }
            if (j == n) return i - j;
            else if (i < m && haystack[i] != needle[j]) {
                if (j != 0) j = lps[j - 1];
                else i++;
            }
        }
        return -1;
    }
    void computeLPSArray(string needle, int n, int[] lps) {
        int length = 0;
        lps[0] = 0;
        int i = 1;
        while (i < n) {
            if (needle[i] == needle[length]) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
    }
    public static void Main() {
        Solution sol = new Solution();
        Console.WriteLine(sol.StrStr("sadbutsad", "sad")); // Output: 0
    }
}

The Python code implements the KMP algorithm, using an LPS array to efficiently find the needle in the haystack.

Complexity

Time Complexity: O(m + n), where m is the length of haystack and n is the length of needle.
Space Complexity: O(n).

Try this approach in the editor

Approach 3: Traversal

We compare the string needle with each character of the string haystack as the starting point. If we find a matching index, we return it directly.

Assuming the length of the string haystack is n and the length of the string needle is m, the time complexity is O((n-m) times m), and the space complexity is O(1).

function strStr(haystack: string, needle: string): number {
    const m = haystack.length;
    const n = needle.length;
    for (let i = 0; i <= m - n; i++) {
        let isEqual = true;
        for (let j = 0; j < n; j++) {
            if (haystack[i + j] !== needle[j]) {
                isEqual = false;
                break;
            }
        }
        if (isEqual) {
            return i;
        }
    }
    return -1;
}
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
}
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let haystack = haystack.as_bytes();
        let needle = needle.as_bytes();
        let m = haystack.len();
        let n = needle.len();
        let mut next = vec![0; n];
        let mut j = 0;
        for i in 1..n {
            while j > 0 && needle[i] != needle[j] {
                j = next[j - 1];
            }
            if needle[i] == needle[j] {
                j += 1;
            }
            next[i] = j;
        }
        j = 0;
        for i in 0..m {
            while j > 0 && haystack[i] != needle[j] {
                j = next[j - 1];
            }
            if haystack[i] == needle[j] {
                j += 1;
            }
            if j == n {
                return (i - n + 1) as i32;
            }
        }
        -1
    }
}
class Solution {
    /**
     * @param String $haystack
     * @param String $needle
     * @return Integer
     */
    function strStr($haystack, $needle) {
        $strNew = str_replace($needle, '+', $haystack);
        $cnt = substr_count($strNew, '+');
        if ($cnt > 0) {
            for ($i = 0; $i < strlen($strNew); $i++) {
                if ($strNew[$i] == '+') {
                    return $i;
                }
            }
        } else {
            return -1;
        }
    }
}
Try this approach in the editor

Approach 4: Rabin-Karp String Matching Algorithm

The Rabin-Karp algorithm essentially uses a sliding window combined with a hash function to compare the hashes of fixed-length strings, which can reduce the time complexity of comparing whether two strings are the same to O(1).

Assuming the length of the string haystack is n and the length of the string needle is m, the time complexity is O(n+m), and the space complexity is O(1).

function strStr(haystack: string, needle: string): number {
    const m = haystack.length;
    const n = needle.length;
    const next = new Array(n).fill(0);
    let j = 0;
    for (let i = 1; i < n; i++) {
        while (j > 0 && needle[i] !== needle[j]) {
            j = next[j - 1];
        }
        if (needle[i] === needle[j]) {
            j++;
        }
        next[i] = j;
    }
    j = 0;
    for (let i = 0; i < m; i++) {
        while (j > 0 && haystack[i] !== needle[j]) {
            j = next[j - 1];
        }
        if (haystack[i] === needle[j]) {
            j++;
        }
        if (j === n) {
            return i - n + 1;
        }
    }
    return -1;
}
func strStr(haystack string, needle string) int {
	n, m := len(haystack), len(needle)
	sha, target, left, right, mod := 0, 0, 0, 0, 1<<31-1
	multi := 1
	for i := 0; i < m; i++ {
		target = (target*256%mod + int(needle[i])) % mod
	}
	for i := 1; i < m; i++ {
		multi = multi * 256 % mod
	}

	for ; right < n; right++ {
		sha = (sha*256%mod + int(haystack[right])) % mod
		if right-left+1 < m {
			continue
		}
		// 此时 left~right 的长度已经为 needle 的长度 m 了，只需要比对 sha 值与 target 是否一致即可
		// 为避免 hash 冲突，还需要确保 haystack[left:right+1] 与 needle 相同
		if sha == target && haystack[left:right+1] == needle {
			return left
		}
		// 未匹配成功，left 右移一位
		sha = (sha - (int(haystack[left])*multi)%mod + mod) % mod
		left++
	}
	return -1
}
Try this approach in the editor

Approach 5: KMP String Matching Algorithm

function strStr(haystack: string, needle: string): number {
    const m = haystack.length;
    const n = needle.length;
    const next = new Array(n).fill(0);
    let j = 0;
    for (let i = 1; i < n; i++) {
        while (j > 0 && needle[i] !== needle[j]) {
            j = next[j - 1];
        }
        if (needle[i] === needle[j]) {
            j++;
        }
        next[i] = j;
    }
    j = 0;
    for (let i = 0; i < m; i++) {
        while (j > 0 && haystack[i] !== needle[j]) {
            j = next[j - 1];
        }
        if (haystack[i] === needle[j]) {
            j++;
        }
        if (j === n) {
            return i - n + 1;
        }
    }
    return -1;
}
func strStr(haystack string, needle string) int {
	n, m := len(haystack), len(needle)
	sha, target, left, right, mod := 0, 0, 0, 0, 1<<31-1
	multi := 1
	for i := 0; i < m; i++ {
		target = (target*256%mod + int(needle[i])) % mod
	}
	for i := 1; i < m; i++ {
		multi = multi * 256 % mod
	}

	for ; right < n; right++ {
		sha = (sha*256%mod + int(haystack[right])) % mod
		if right-left+1 < m {
			continue
		}
		// 此时 left~right 的长度已经为 needle 的长度 m 了，只需要比对 sha 值与 target 是否一致即可
		// 为避免 hash 冲突，还需要确保 haystack[left:right+1] 与 needle 相同
		if sha == target && haystack[left:right+1] == needle {
			return left
		}
		// 未匹配成功，left 右移一位
		sha = (sha - (int(haystack[left])*multi)%mod + mod) % mod
		left++
	}
	return -1
}
impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let haystack = haystack.as_bytes();
        let needle = needle.as_bytes();
        let m = haystack.len();
        let n = needle.len();
        let mut next = vec![0; n];
        let mut j = 0;
        for i in 1..n {
            while j > 0 && needle[i] != needle[j] {
                j = next[j - 1];
            }
            if needle[i] == needle[j] {
                j += 1;
            }
            next[i] = j;
        }
        j = 0;
        for i in 0..m {
            while j > 0 && haystack[i] != needle[j] {
                j = next[j - 1];
            }
            if haystack[i] == needle[j] {
                j += 1;
            }
            if j == n {
                return (i - n + 1) as i32;
            }
        }
        -1
    }
}
class Solution {
    /**
     * @param String $haystack
     * @param String $needle
     * @return Integer
     */
    function strStr($haystack, $needle) {
        $strNew = str_replace($needle, '+', $haystack);
        $cnt = substr_count($strNew, '+');
        if ($cnt > 0) {
            for ($i = 0; $i < strlen($strNew); $i++) {
                if ($strNew[$i] == '+') {
                    return $i;
                }
            }
        } else {
            return -1;
        }
    }
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O((m-n+1)*n), where m is the length of haystack and n is the length of needle.
Space Complexity: O(1).

KMP Algorithm

Time Complexity: O(m + n), where m is the length of haystack and n is the length of needle.
Space Complexity: O(n).

Traversal–
Rabin-Karp String Matching Algorithm–
KMP String Matching Algorithm–

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force ComparisonO(n * m)O(1)Simple implementation, small inputs, or when explaining the baseline approach in interviews
KMP AlgorithmO(n + m)O(m)Large strings or repeated patterns where avoiding redundant comparisons significantly improves performance

Frequently asked questions

Is Find the Index of the First Occurrence in a String easy or hard?

The problem is classified as Easy because the brute force solution is straightforward to implement. However, discussing or implementing the KMP algorithm demonstrates deeper knowledge of string matching techniques.

Find the Index of the First Occurrence in a String Python/Java solution

In Python or Java, the brute force solution iterates through each possible starting index and compares characters until the substring matches or fails. The optimized implementation builds the KMP LPS array and performs a linear scan, achieving O(n + m) time complexity.

How to solve Find the Index of the First Occurrence in a String in O(n)?

Use the KMP string matching algorithm. First compute the LPS (Longest Prefix Suffix) array for the pattern in O(m) time, then scan the main string once while adjusting the pattern index using LPS values. The overall runtime becomes O(n + m).

What is the best approach for Find the Index of the First Occurrence in a String?

The most efficient approach is the KMP (Knuth–Morris–Pratt) algorithm. It preprocesses the pattern to build an LPS array and avoids rechecking characters after mismatches. This guarantees O(n + m) time complexity compared to the O(n * m) brute force approach.

Is Find the Index of the First Occurrence in a String asked at Google/Amazon/Meta?

Substring search problems appear frequently in interviews at large tech companies including Google, Amazon, and Meta. Variants test understanding of string traversal, pattern matching, and algorithms like KMP or Rabin–Karp.

What data structure is used in Find the Index of the First Occurrence in a String?

The problem primarily uses string traversal and index pointers. In the optimized KMP approach, an auxiliary integer array called the LPS (Longest Prefix Suffix) table is used to store prefix information about the pattern.

What is the time complexity of Find the Index of the First Occurrence in a String?

The brute force solution runs in O(n * m) time where n is the length of the main string and m is the length of the substring. The optimized KMP algorithm runs in O(n + m) time by skipping redundant comparisons using the prefix table.

Comments

Next problem · similarShortest PalindromeHard
Now write it yourselfClose this page and solve Find the Index of the First Occurrence in a String in the editor, without looking.
Practise Find the Index of the First Occurrence in a String