Introduction

The Implement strStr() problem involves finding the first occurrence of a substring inside another string.

Given:

  • a string haystack
  • a string needle

the task is to:

  • return the starting index
    of the first occurrence of needle
    inside haystack

If substring does not exist:

  • return -1

This problem helps in understanding:

  • pattern matching
  • substring comparison
  • traversal techniques
  • sliding window concepts

Example

Input:haystack = "hello"needle = "ll"

Output:
2

Explanation:
"ll" starts at index 2.

Input:
haystack = "abcdef"
needle = "gh"

Output:
-1

Explanation:
Substring does not exist.

Constraints

1 <= haystack.length,needle.length <= 10^4
haystack and needle
contain lowercase English letters

Approach 1 : Brute Force

Explanation

The simplest way to solve this problem is:

  1. Check every possible starting index
  2. Compare substring characters one by one
  3. Return matching index

This approach directly follows the problem statement.

Steps

  1. Traverse possible starting positions.
  2. Compare substring characters.
  3. If all characters match:
    • return index
  4. Otherwise continue traversal.
  5. Return -1 if no match exists.

Dry Run

Input:haystack = "hello"needle = "ll"
Check index 0:
"he"
Not matching

Check index 1:
"el"
Not matching

Check index 2:
"ll"
Match found

Final Result:
2

Brute Force Code

Complexity Analysis

Time Complexity: O(n * m)Explanation:
Substring comparison is performed
for every possible position.

Space Complexity: O(1)
Explanation:
No extra data structures are used.

Approach 2 : Optimized Solution (Substring Comparison)

Explanation

The optimized solution uses direct substring extraction.

The idea is:

  1. Extract substring of needle length
  2. Compare directly with needle
  3. Return matching index

This provides cleaner implementation.

Steps

  1. Traverse possible positions.
  2. Extract substring.
  3. Compare with needle.
  4. Return matching index.
  5. Return -1 otherwise.

Dry Run

Input:haystack = "hello"needle = "ll"
Extract substring:
"he"
Not matching

Extract substring:
"el"
Not matching

Extract substring:
"ll"
Match found

Final Result:
2

Optimized Code

Complexity Analysis

Time Complexity: O(n * m)Explanation:
Substring comparison is performed for every window.

Space Complexity: O(m)
Explanation:
Extra substring storage may be used.

Edge Cases

  1. needle is empty
  2. needle longer than haystack
  3. Multiple occurrences exist
  4. Match at beginning
  5. Match at ending

Why This Problem is Important

This problem helps in understanding:

  1. Pattern matching
  2. Sliding window concepts
  3. String traversal
  4. Substring comparison
  5. Sequential matching

It is one of the most common string interview problems.

Real-World Applications

Pattern matching concepts are used in:

  1. Search engines
  2. Text editors
  3. DNA sequence analysis
  4. Compiler design
  5. Data filtering systems

Common Mistakes

  1. Incorrect loop bounds
  2. Index out of range errors
  3. Forgetting no-match case
  4. Wrong substring extraction

Interview Tips

Interviewers often expect:

  1. Proper traversal logic
  2. Efficient substring comparison
  3. Edge case handling

Always explain why traversal stops at:

 n - m

where:

  • n = haystack length
  • m = needle length

Related Questions

  1. Naive Pattern Matching
  2. Minimum Window Substring
  3. Valid Anagram
  4. Reverse String
  5. Longest Substring Without Repeating Characters

Final Takeaway

The Implement strStr() problem is a fundamental pattern matching problem that teaches substring traversal and sequential comparison techniques. Understanding this problem builds a strong foundation for advanced string matching and searching interview problems.