Find the Index of the First Occurrence in a String - Solution & Explanation
Problem Statement
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 <= 104haystackandneedleconsist 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.
This C code uses a naive approach to find the first occurrence of the needle in the haystack. It iterates over possible starting indices, checking if a matching substring can be found.
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).
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.
This C solution uses the KMP algorithm, which preprocesses the needle to create an LPS array, reducing the number of comparisons required.
Complexity
Time Complexity: O(m + n), where m is the length of haystack and n is the length of needle.
Space Complexity: O(n), due to the LPS array.
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).
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
PHP
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).
Code
Go
TypeScript
Approach 5: KMP String Matching Algorithm
Code
C#
Rust
C++
JavaScript
Go
Python
Java
TypeScript
PHP
Complexity Comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O((m-n+1)*n), where m is the length of haystack and n is the length of needle. |
| KMP Algorithm | Time Complexity: O(m + n), where m is the length of haystack and n is the length of needle. |
| Traversal | — |
| Rabin-Karp String Matching Algorithm | — |
| KMP String Matching Algorithm | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Comparison | O(n * m) | O(1) | Simple implementation, small inputs, or when explaining the baseline approach in interviews |
| KMP Algorithm | O(n + m) | O(m) | Large strings or repeated patterns where avoiding redundant comparisons significantly improves performance |
Video Solution
Knuth–Morris–Pratt KMP - Find the Index of the First Occurrence in a String - Leetcode 28 - Python • NeetCode • 195,453 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find the Index of the First Occurrence in a String easy or hard?
Find the Index of the First Occurrence in a String Python/Java solution
How to solve Find the Index of the First Occurrence in a String in O(n)?
What is the best approach for Find the Index of the First Occurrence in a String?
Is Find the Index of the First Occurrence in a String asked at Google/Amazon/Meta?
What data structure is used in Find the Index of the First Occurrence in a String?
What is the time complexity of Find the Index of the First Occurrence in a String?
Ready to solve this problem?
Practice Find the Index of the First Occurrence in a String with our built-in code editor and test cases.
Practice on FleetCode