Leetcode 28: Find the Index of the First Occurrence in a String

1. Problem Statement (Simple Explanation):

You are given two strings:

haystack: the main string
needle: the substring to search for

Return:

The index of the first occurrence of needle in haystack.
If needle is not part of haystack, return -1.

Indexing is 0-based.

2. Examples:

Example 1:

Input:

haystack = "sadbutsad"

needle = "sad"

Occurrences of "sad":

At index 0: "sad"butsad
At index 6: sadb ut"sad"

First occurrence is at index 0.

Output: 0

Example 2:

Input:

haystack = "leetcode"

needle = "leeto"

"leeto" does not appear in "leetcode".

Output: -1

Constraints:

1 <= haystack.length, needle.length <= 104
Both strings consist of only lowercase English letters.

3. Approach – Simple Sliding Window (Brute Force, O(n·m)):

Given constraints up to 104, a straightforward O(n·m) solution is acceptable.

Let:

n = len(haystack)
m = len(needle)

We check all possible starting indices i in haystack where needle might fit:

Valid start positions: i from 0 to n - m.

For each i, check if:

haystack[i .. i+m-1] == needle[0 .. m-1]
If yes, return i.
If none matches, return -1.

Edge Cases:

If needle is longer than haystack (m > n): it cannot occur → return -1.
(In some variations, if needle is empty, they return 0, but here constraints say length ≥ 1, so no need.)

Pseudo-code:

Complexity:

Time: O(n-m) in worst case.
Space: O(1) extra.
For n, m ≤ 104, this is fine in practice.

4. Java code:

5. C code:

6. C++ code:

7. Python code:

(Here we leverage Python slicing for clarity; under the hood it’s similar to the inner loop.)

8. JavaScript code:

Comments

Leetcode 1: Two Sum

Leetcode Link: https://leetcode.com/problems/two-sum/ 1. Problem Statement (Simple Explanation) You are given: An array of integers nums An integer target You need to return the indices of two numbers in the array such that: Conditions: Each input has exactly one solution . You cannot use the same element twice . You can return the answer in any order . 2. Examples Example 1 Input: nums = [2, 7, 11, 15], target = 9 Output: [0, 1] Explanation: nums[0]+nums[1]=2+7=9 So we return [0, 1]. Example 2 Input: ...

Leetcode 3: Longest Substring Without Repeating Characters

Leetcode Link 1. Problem Statement (Simple Explanation) You are given a string s. You need to find the length of the longest substring of s that does not contain any repeated characters. A substring is a contiguous sequence of characters in the string. You must return an integer length, not the substring itself. 2. Examples Example 1 Input: s = "abcabcbb" Output: 3 Explanation: Some substrings without repeating characters: "abc", "bca", "cab"The longest length is 3. Example 2 Input: s = "bbbbb" Output: 1 Explanation: All substrings that are valid are just "b". The longest length is 1. Example 3 Input: s = "pwwkew" Output: 3 Explanation: Possible substrings without repetition: "pw", "wke", "kew". "wke" or "kew" have length 3. "pwke" is not valid because it’s not contiguous in the original string (p and k are separated by ww). Constraints...

Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/ 1. Problem Statement (Simple Explanation) You are given two non-empty linked lists , l1 and l2, that represent two non-negative integers. Each node contains a single digit . The digits are stored in reverse order (i.e., the 1’s digit is at the head). You need to add the two numbers and return the sum as a linked list , also in reverse order. You can assume: There are no leading zeros , except when the number itself is 0. 2. Examples Example 1 Input: l1 = [2,4,3] l2 = [5,6,4] Interpreting linked lists as numbers (reverse order): l1 represents 342 l2 represents 465 Output: [7,0,8] Explanation: ...

codesprint with rishav

Search This Blog