Find the Index of the First Occurrence in a String

Length of Last Word

Valid Parentheses

Return the starting index of the first exact occurrence of one string inside another.

Return the zero-based index of the first exact occurrence of `sub` inside `s`. Return `-1` when it does not occur. By convention, an empty `sub` matches at index `0`.

**Input / output**
- Input: `s: string`, `sub: string`
- Output: integer index

**Examples**
1. `s = "mississippi", sub = "iss"` returns `1`.
2. `s = "abcdef", sub = "gh"` returns `-1`.

**Constraints**
- `0 <= s.length, sub.length <= 100,000`
- Matching is case-sensitive.

**Follow-up**
When would KMP or another linear-time matcher be worth the preprocessing cost over a direct scan?

- Return the first index where `sub` appears inside `s`.
- If there is no matching position, return `-1`.
- If `sub` is empty, the conventional first occurrence is index `0`.

Understand the Match Requirement

- A substring of length `m` can only start at indices `0` through `len(s) - m`.
- For each start index, compare the next `m` characters with `sub`.
- The first full match is the answer.

Try Each Possible Start Index

- Stop the loop at `len(s) - len(sub)` so every checked slice has enough characters.
- If `sub` is longer than `s`, the range is empty and the function returns `-1`.
- This keeps the control flow simple.

Avoid Out-of-Bounds Checks

- Slicing is concise, but you can also compare characters one by one.
- Stop early when a mismatch appears.
- This is the same basic brute-force string search idea.

Manual Character Comparison Option

- The final solution checks the empty substring case, then tests each possible starting position.
- Time complexity is O(n * m), where `n` is `len(s)` and `m` is `len(sub)`.
- Space complexity is O(1), ignoring the temporary slice used for comparison.