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 <= 104haystack and needle consist of only lowercase English characters.In #28 Find the Index of the First Occurrence in a String, you are given two strings: a larger text (often called haystack) and a smaller pattern (needle). The goal is to return the index of the first position where the pattern appears in the text, or -1 if it does not exist.
A straightforward way to solve this is by using a two-pointer comparison. Iterate through each possible starting position in the main string and compare characters of the pattern one by one. If all characters match, return that starting index. If a mismatch occurs, move the starting pointer forward and try again.
This approach works well for interview settings and is simple to implement. Its time complexity is O(n * m), where n is the length of the main string and m is the length of the pattern.
For more advanced scenarios, optimized string matching algorithms such as KMP (Knuth–Morris–Pratt) can reduce repeated comparisons and achieve O(n + m) time complexity.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Brute Force / Two Pointers | O(n * m) | O(1) |
| KMP String Matching | O(n + m) | O(m) |
NeetCode
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.
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).
1#include <stdio.h>
2#include <string.h>
3
4int strStr(char * haystack, char * needle) {
5
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.
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.
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.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
String matching problems evaluate a candidate’s ability to handle character-level comparisons, edge cases, and algorithmic optimization. They also introduce important algorithms such as KMP, Rabin–Karp, and other pattern matching techniques.
Yes, this problem or its variations frequently appear in coding interviews at major tech companies. It tests understanding of string traversal, pattern matching, and the ability to optimize naive solutions.
No special data structure is strictly required for the basic solution. Most implementations rely on simple string traversal using indices or two pointers. Advanced algorithms like KMP may use an auxiliary array (LPS table) to store prefix information.
The simplest approach is a brute-force comparison where you check every possible starting index in the main string and compare characters with the pattern. For optimal performance in larger inputs, the KMP (Knuth–Morris–Pratt) algorithm can be used to achieve linear time complexity.
This C solution uses the KMP algorithm, which preprocesses the needle to create an LPS array, reducing the number of comparisons required.