Find the Index of First Occurrence in a String

69.1k
0

Given two strings haystack and needle, find the index of the first occurrence of needle in haystack.

If needle is not present in haystack, return -1.

Example 1

Input: haystack = "sadbutsad", needle = "sad"

Output: 0

Explanation: The string "sad" appears at index 0 and index 6. Since the first occurrence is at index 0, the answer is 0.

Example 2

Input: haystack = "leetcode", needle = "leeto"

Output: -1

Explanation: The string "leeto" does not appear inside "leetcode", so the answer is -1.

Brute Force Approach

The most direct idea is to try placing needle at every possible starting index of haystack. For each starting index, compare characters one by one:

  • compare the first character of needle

  • then the second character

  • keep going until either all characters match or one mismatch appears

If all characters of needle match from a starting index, that index is the answer. Since starting indices are checked from left to right, the first successful match is automatically the first occurrence.

The only careful detail is the stopping point. If needle has length m and haystack has length n, then the last useful starting index is n - m. After that, not enough characters are left to fit the whole needle.

Algorithm

  • Store the lengths of both strings because the loop boundaries depend on how much space is needed to fit needle.

  • If needle is empty, return 0. This follows the common strStr convention that an empty pattern is found at the beginning.

  • If needle is longer than haystack, return -1 because the smaller string cannot fit inside the bigger search space.

  • Try every starting index from 0 to n - m. This checks only positions where the full needle can still fit.

  • For each starting index, compare characters of needle with the matching characters of haystack.

  • If all m characters match, return the current starting index because the scan is moving left to right.

  • If no starting index gives a complete match, return -1.

Dry Run

Find the Index of First Occurrence in a String Brute Dry Run

Find the Index of First Occurrence in a String Brute Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
/*
Returns the first index where needle appears
inside haystack using direct character matching.
*/
int strStr(string haystack, string needle) {
// These lengths decide the valid search range.
int n = haystack.length();
int m = needle.length();
// An empty pattern is treated as found
// at the beginning of the string.
if (m == 0) {
return 0;
}
// If the pattern is longer, it cannot fit
// inside the text at any starting index.
if (m > n) {
return -1;
}
for (int start = 0; start <= n - m; start++) {
// This counts how many characters matched
// from the current starting index.
int matched = 0;
// Keep matching while characters are equal
// and the pattern still has characters left.
while (matched < m &&
haystack[start + matched] == needle[matched]) {
matched++;
}
// If every character matched, this is the
// first occurrence because scanning is left to right.
if (matched == m) {
return start;
}
}
return -1;
}
};
// Driver code starts
int main() {
string haystack = "sadbutsad";
string needle = "sad";
Solution sol;
cout << sol.strStr(haystack, needle) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N * M), where N is the length of haystack and M is the length of needle. In the worst case, many starting positions may compare many characters.

Space Complexity: O(1), because constant space is used.

Optimal Approach

The brute force approach has one repeated habit: after a mismatch, it often starts over even though some characters were already matched.

For example, suppose the pattern is "abab" and some prefix of it has already matched. If a mismatch happens, the matched part may still contain a smaller prefix that can be reused. KMP uses this observation.

KMP builds an LPS array for needle.

LPS means Longest Prefix Suffix. For every index in needle, it stores the length of the longest proper prefix that is also a suffix ending at that index.

That sounds a bit formal, so here is the friendly version: the LPS array tells how much of the pattern can still be kept after a mismatch.

Instead of moving the text pointer backward or rechecking characters from scratch, KMP moves only the pattern pointer to a useful previous position. This is why each character is processed only a small number of times.

Algorithm

  • Handle simple cases first.
    If needle is empty, return 0. If needle is longer than haystack, return -1.
    Why? A longer pattern cannot fit inside the text, and an empty pattern is considered to occur at index 0.

  • Build the LPS array for needle.
    LPS[i] stores the length of the longest proper prefix of needle[0...i] that is also a suffix.
    Why? When a mismatch occurs, LPS tells us how much of the pattern is still potentially useful, so we don't have to start matching from the beginning.

  • Use two pointers: textIndex for haystack and patternIndex for needle.
    Why? They represent the characters currently being compared.

  • When the characters match, move both pointers forward.
    Why? The current characters are successfully matched, so we can continue checking the next characters.

  • When the entire pattern is matched, return textIndex - patternLength.
    Why? textIndex has already moved past the last matched character, so subtracting the pattern length gives the starting index of the match.

  • When a mismatch occurs after some pattern characters have matched, update patternIndex = LPS[patternIndex - 1].
    Why? The already-matched part contains a prefix that can also act as the beginning of a new match. LPS tells us exactly where to continue, avoiding unnecessary comparisons.

  • When a mismatch occurs at patternIndex = 0, move textIndex forward.
    Why? No part of the pattern has matched, so there is nothing to reuse. We simply try the next character of the text.

Dry Run

Implement Strstr Optimal Dry Run

Implement Strstr Optimal Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
/*
Builds the LPS array that tells where the
pattern pointer should move after a mismatch.
*/
vector<int> buildLPS(string& needle) {
int m = needle.length();
// lps[i] stores the longest proper prefix
// that is also a suffix for needle[0..i].
vector<int> lps(m, 0);
// This stores the length of the current
// matching prefix-suffix.
int length = 0;
// The first LPS value is always 0,
// so building starts from index 1.
int index = 1;
while (index < m) {
// Matching characters extend the current
// prefix-suffix by one character.
if (needle[index] == needle[length]) {
length++;
lps[index] = length;
index++;
} else {
// If a smaller prefix-suffix exists,
// try that length before giving up.
if (length != 0) {
length = lps[length - 1];
} else {
// No prefix-suffix can be reused
// for this index, so it stays 0.
lps[index] = 0;
index++;
}
}
}
return lps;
}
public:
/*
Returns the first index where needle appears
inside haystack using the KMP algorithm.
*/
int strStr(string haystack, string needle) {
int n = haystack.length();
int m = needle.length();
// An empty pattern is treated as found
// at the beginning of the string.
if (m == 0) {
return 0;
}
// If the pattern is longer, it cannot fit
// inside the text at any starting index.
if (m > n) {
return -1;
}
// The LPS array helps skip repeated comparisons.
vector<int> lps = buildLPS(needle);
// This pointer moves through the main string.
int textIndex = 0;
// This pointer moves through the pattern string.
int patternIndex = 0;
while (textIndex < n) {
// Matching characters mean the current
// candidate substring is still valid.
if (haystack[textIndex] == needle[patternIndex]) {
textIndex++;
patternIndex++;
// A full pattern match ends at textIndex - 1,
// so the starting index is textIndex - m.
if (patternIndex == m) {
return textIndex - m;
}
} else {
// If some characters matched earlier,
// reuse the longest useful prefix.
if (patternIndex != 0) {
patternIndex = lps[patternIndex - 1];
} else {
// No partial match exists, so move
// to the next character in haystack.
textIndex++;
}
}
}
return -1;
}
};
// Driver code starts
int main() {
string haystack = "sadbutsad";
string needle = "sad";
Solution sol;
cout << sol.strStr(haystack, needle) << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N + M), because the LPS array is built once and the matching scan processes the strings linearly.

Space Complexity: O(M), because the LPS array stores one value for each character of needle.

Interview follow-up Questions

Starting after n - m leaves fewer than m characters in haystack. Since the full needle cannot fit there, those positions do not need to be checked.

String

Read Similar Blogs

TrieRecursionArraysData StructuresString

Word Search II

Input: board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"] Output: ["oath","eat"] Explanation: The words "oath" and "eat" can be f...

100.8k
StringRecursionArrays

Introduction to String Advanced

1. Basic Pattern Matching Problem Suppose a word needs to be searched inside a larger sentence or string. The goal is to find all starting positions where the smaller pattern exactly matches a part...

66.9k
String

Introduction to Prefix-Suffix in String

Input: s = "ababab" Output: 4 Explanation: The prefix "abab" and the suffix "abab" are the same, so the longest prefix-suffix length is 4 . Input: s = "aabcdaabc" Output: 4 Explanation: The string...

81.6k
Comments0