Find First Occurrence in String

Given two strings s and t, return the index of the first occurrence of t within s if it exists; otherwise, return -1.

Note: This is equivalent to implementing the strStr() or indexOf() function.

Example(s)

Example 1:

Input: s = "abc", t = "a"
Output: 0
Explanation: "a" is found at index 0 in "abc".

Example 2:

Input: s = "abc", t = "abcd"
Output: -1
Explanation: "abcd" is longer than "abc", so it cannot be found.

Example 3:

Input: s = "sadbutsad", t = "sad"
Output: 0
Explanation: "sad" is found at index 0 in "sadbutsad".

Example 4:

Input: s = "leetcode", t = "leeto"
Output: -1
Explanation: "leeto" is not found in "leetcode".

Example 5:

Input: s = "hello", t = "ll"
Output: 2
Explanation: "ll" is found at index 2 in "hello".

Solution

The solution uses sliding window approach:

Edge cases: If t is empty, return 0. If t is longer than s, return -1.
Sliding window: For each possible starting position in s, check if t matches
Character comparison: Compare characters of s and t at each position
Early termination: If a mismatch is found, move to next position
Return index: If all characters match, return the starting index

JavaScript Solution
Python Solution

JavaScript Solution - Brute Force

/**
* Find the first occurrence of t in s
* @param {string} s - Haystack string
* @param {string} t - Needle string
* @return {number} - Index of first occurrence, or -1 if not found
*/
function strStr(s, t) {
// Edge cases
if (t.length === 0) return 0;
if (t.length > s.length) return -1;

// Try each possible starting position in s
for (let i = 0; i <= s.length - t.length; i++) {
  let j = 0;
  
  // Check if t matches starting at position i
  while (j < t.length && s[i + j] === t[j]) {
    j++;
  }
  
  // If we matched all characters of t, return i
  if (j === t.length) {
    return i;
  }
}

return -1;
}

// Test cases
console.log('Example 1:', strStr("abc", "a")); // 0
console.log('Example 2:', strStr("abc", "abcd")); // -1
console.log('Example 3:', strStr("sadbutsad", "sad")); // 0
console.log('Example 4:', strStr("leetcode", "leeto")); // -1
console.log('Example 5:', strStr("hello", "ll")); // 2
console.log('Test 6:', strStr("", "")); // 0
console.log('Test 7:', strStr("a", "a")); // 0

Output:

Click "Run Code" to execute the code and see the results.

Python Solution - Brute Force

def str_str(s: str, t: str) -> int:
  """
  Find the first occurrence of t in s
  
  Args:
      s: Haystack string
      t: Needle string
      
  Returns:
      int: Index of first occurrence, or -1 if not found
  """
  # Edge cases
  if len(t) == 0:
      return 0
  if len(t) > len(s):
      return -1
  
  # Try each possible starting position in s
  for i in range(len(s) - len(t) + 1):
      # Check if t matches starting at position i
      if s[i:i + len(t)] == t:
          return i
  
  return -1

# Test cases
print('Example 1:', str_str("abc", "a"))  # 0
print('Example 2:', str_str("abc", "abcd"))  # -1
print('Example 3:', str_str("sadbutsad", "sad"))  # 0
print('Example 4:', str_str("leetcode", "leeto"))  # -1
print('Example 5:', str_str("hello", "ll"))  # 2
print('Test 6:', str_str("", ""))  # 0
print('Test 7:', str_str("a", "a"))  # 0

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Alternative Solution (Built-in Method)

Most languages have built-in methods, but for learning purposes, here's a cleaner implementation:

JavaScript Built-in
Python Built-in

/**
 * Using built-in indexOf (for reference)
 */
function strStrBuiltIn(s, t) {
  return s.indexOf(t);
}

def str_str_builtin(s: str, t: str) -> int:
    """
    Using built-in find (for reference)
    """
    return s.find(t)

Advanced Solution (KMP Algorithm)

For better performance on large inputs, we can use the KMP (Knuth-Morris-Pratt) algorithm:

JavaScript KMP
Python KMP

/**
 * KMP Algorithm - O(n + m) time complexity
 */
function strStrKMP(s, t) {
  if (t.length === 0) return 0;
  if (t.length > s.length) return -1;
  
  // Build failure function (LPS - Longest Proper Prefix which is also Suffix)
  function buildLPS(pattern) {
    const lps = new Array(pattern.length).fill(0);
    let len = 0;
    let i = 1;
    
    while (i < pattern.length) {
      if (pattern[i] === pattern[len]) {
        len++;
        lps[i] = len;
        i++;
      } else {
        if (len !== 0) {
          len = lps[len - 1];
        } else {
          lps[i] = 0;
          i++;
        }
      }
    }
    
    return lps;
  }
  
  const lps = buildLPS(t);
  let i = 0; // index for s
  let j = 0; // index for t
  
  while (i < s.length) {
    if (s[i] === t[j]) {
      i++;
      j++;
    }
    
    if (j === t.length) {
      return i - j; // Found match
    } else if (i < s.length && s[i] !== t[j]) {
      if (j !== 0) {
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }
  
  return -1;
}

def str_str_kmp(s: str, t: str) -> int:
    """
    KMP Algorithm - O(n + m) time complexity
    """
    if len(t) == 0:
        return 0
    if len(t) > len(s):
        return -1
    
    # Build failure function (LPS)
    def build_lps(pattern: str) -> List[int]:
        lps = [0] * len(pattern)
        length = 0
        i = 1
        
        while i < len(pattern):
            if pattern[i] == pattern[length]:
                length += 1
                lps[i] = length
                i += 1
            else:
                if length != 0:
                    length = lps[length - 1]
                else:
                    lps[i] = 0
                    i += 1
        
        return lps
    
    lps = build_lps(t)
    i = 0  # index for s
    j = 0  # index for t
    
    while i < len(s):
        if s[i] == t[j]:
            i += 1
            j += 1
        
        if j == len(t):
            return i - j  # Found match
        elif i < len(s) and s[i] != t[j]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    
    return -1

Complexity

Time Complexity:
- Brute Force: O(n × m) - Where n is length of s and m is length of t. In the worst case, we compare m characters for each of n positions.
- KMP Algorithm: O(n + m) - Linear time complexity.
Space Complexity:
- Brute Force: O(1) - Only uses a constant amount of extra space.
- KMP Algorithm: O(m) - For the LPS (Longest Proper Prefix which is also Suffix) array.

Approach

The brute force solution uses a sliding window:

Edge case handling:
- If t is empty, return 0
- If t is longer than s, return -1
Sliding window: For each position i in s from 0 to s.length - t.length:
- Check if t matches starting at position i
- Compare characters one by one
Character matching:
- Use a nested loop to compare s[i + j] with t[j]
- If all characters match, return i
Return -1: If no match is found after checking all positions

Key Insights

Sliding window: Try each possible starting position
Early termination: Stop comparing as soon as a mismatch is found
Boundary check: Only check positions where t can fit (i ≤ s.length - t.length)
KMP optimization: For repeated patterns, KMP avoids re-checking characters
Built-in methods: Most languages have optimized implementations

Step-by-Step Example

Let's trace through Example 3: s = "sadbutsad", t = "sad"

Initial: s = "sadbutsad", t = "sad"
         i = 0, t.length = 3, s.length = 9

Position i = 0:
  Compare s[0] with t[0]: 's' === 's' ✓
  Compare s[1] with t[1]: 'a' === 'a' ✓
  Compare s[2] with t[2]: 'd' === 'd' ✓
  All characters match!
  Return 0

Result: 0

Let's trace through Example 4: s = "leetcode", t = "leeto"

Initial: s = "leetcode", t = "leeto"
         i = 0, t.length = 5, s.length = 8

Position i = 0:
  Compare s[0] with t[0]: 'l' === 'l' ✓
  Compare s[1] with t[1]: 'e' === 'e' ✓
  Compare s[2] with t[2]: 'e' === 'e' ✓
  Compare s[3] with t[3]: 't' === 't' ✓
  Compare s[4] with t[4]: 'c' !== 'o' ✗
  Mismatch, try next position

Position i = 1:
  Compare s[1] with t[0]: 'e' !== 'l' ✗
  Mismatch, try next position

Position i = 2:
  Compare s[2] with t[0]: 'e' !== 'l' ✗
  Mismatch, try next position

Position i = 3:
  Compare s[3] with t[0]: 't' !== 'l' ✗
  Mismatch, try next position

Position i = 4:
  Compare s[4] with t[0]: 'c' !== 'l' ✗
  Mismatch, try next position

No more positions (i > 8 - 5 = 3, but we check i = 0 to 3)
Wait, we need to check i = 0 to 3 (inclusive)

Actually, we check i from 0 to s.length - t.length = 8 - 5 = 3
So we check positions 0, 1, 2, 3

After checking all positions, no match found.
Return -1

Edge Cases

Empty needle: t = "" → Return 0 (empty string is found at index 0)
Empty haystack: s = "", t = "a" → Return -1
Both empty: s = "", t = "" → Return 0
Needle longer: s = "abc", t = "abcd" → Return -1
Needle equals haystack: s = "abc", t = "abc" → Return 0
Multiple occurrences: s = "sadbutsad", t = "sad" → Return 0 (first occurrence)
No match: s = "leetcode", t = "leeto" → Return -1

When to Use KMP

Use KMP algorithm when:

Large inputs: When s and t are very long
Repeated patterns: When t has repeated subpatterns
Performance critical: When brute force is too slow

For most cases, brute force is sufficient and simpler to understand.

Repeated Substring Pattern: Check if string can be constructed by repeating a substring
Longest Common Prefix: Find common prefix among strings
Valid Anagram: Check if two strings are anagrams
String Compression: Compress string using character counts

Takeaways

Brute force is simple and works for most cases
Sliding window pattern is common for substring problems
Edge cases are important (empty strings, length checks)
KMP algorithm provides O(n + m) time but is more complex
Built-in methods are optimized but understanding the algorithm is valuable

Example(s)​

Solution​

JavaScript Solution - Brute Force

Output:

Python Solution - Brute Force

Output:

Alternative Solution (Built-in Method)​

Advanced Solution (KMP Algorithm)​

Complexity​

Approach​

Key Insights​

Step-by-Step Example​

Edge Cases​

When to Use KMP​

Related Problems​

Takeaways​

Example(s)

Solution

Alternative Solution (Built-in Method)

Advanced Solution (KMP Algorithm)

Complexity

Approach

Key Insights

Step-by-Step Example

Edge Cases

When to Use KMP

Related Problems

Takeaways