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

**Difficulty**: `Easy` - **Tags**: `String`, `Two Pointers`

[LeetCode Problem Link](https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/)

## Description

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`.

## Examples

**Example 1:**

Input:

```python
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:

```python
haystack = "leetcode"
needle = "leeto"
```

Output:

```
-1
```

Explanation: "leeto" did not occur in "leetcode", so we return -1.

## Constraints

* The strings `haystack` and `needle` consist of lowercase English letters.

## Solution 💡

To solve this problem manually (without using built-in methods like `indexOf`), we can use a sliding window technique. We check each substring in `haystack` of the same length as `needle` and compare it with `needle`. If a match is found, return the starting index. If no match is found, return `-1`.

### Java

```java
class Solution {
    public int strStr(String haystack, String needle) {
        int hLen = haystack.length();
        int nLen = needle.length();

        // If needle is empty, return 0
        if (nLen == 0) {
            return 0;
        }

        // Loop through haystack and check substrings of length equal to needle
        for (int i = 0; i <= hLen - nLen; i++) {
            // Check if substring matches the needle
            if (haystack.substring(i, i + nLen).equals(needle)) {
                return i;
            }
        }

        // If no match is found, return -1
        return -1;
    }
}
```

### Time Complexity ⏳

* **O(n \* m)**: The time complexity is O(n \* m), where `n` is the length of the `haystack` and `m` is the length of the `needle`. For each starting index in `haystack`, we compare up to `m` characters.

### Space Complexity 💾

* **O(1)**: We only use constant space for variables, as no additional space is needed beyond the input strings.

You can find the full solution [here](https://github.com/ChunhThanhDe/Leetcode-Top-Interview/blob/main/Topic%201%20Array%20-%20String/023%20Find%20the%20Index%20of%20the%20First%20Occurrence%20in%20a%20String/Solution.java).


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://chunhthanhde.gitbook.io/leetcode-top-interview/topic-1-array-string/023-find-the-index-of-the-first-occurrence-in-a-string.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.