20. Implement strstr()

You’re interviewing for a backend or data engineering role at a FAANG-level company. The interviewer describes a real product scenario:

A large search, logging, or content processing platform frequently scans text to locate smaller patterns. Examples include:

• finding keywords in search queries
• matching filters in log files
• detecting banned words in content
• locating tokens in configuration strings

The system receives two strings:

• a main text string haystack
• a smaller pattern string needle

The platform needs to find the first occurrence of needle inside haystack. If the pattern does not exist, the system should return -1.

This is a common practice coding problem for DSA question might ask in Google, Amazon, Netflix, Meta, Apple, Microsoft, Uber, and Bloomberg interviews.

Your Task

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

If needle is not part of haystack, return -1.

If needle is an empty string, return 0.

Input Format

• haystack: a string representing the main text
• needle: a string representing the pattern to search for

Output Format

• A single integer representing the index of the first occurrence of needle in haystack
• Return -1 if no occurrence exists

Examples

Constraints

• 0 <= haystack.length <= 100,000
• 0 <= needle.length <= 100,000
• Both strings consist of lowercase English letters