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.

Description Solution Video 35:52

28. Find the Index of the First Occurrence in a String

Q: 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.

Easy47.0% acceptance16 companies

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 <= 10⁴
haystack and needle consist of only lowercase English characters.

Asked at 16 companies

Pocket Gems Lg Electronics Amazon Microsoft Bloomberg Apple

TCS Expedia Qualcomm Capgemini

Google Meta

+4 more

Zoho

Infosys PayPal LinkedIn

Topics

35:52

Still stuck?Read 5 approaches, or watch a walkthrough.

Open solution

28. Find the Index of the First Occurrence in a String

Asked at 16 companies

Topics

Similar problems