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:

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

JavaScript 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

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

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

Python Built-in

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

/**
 * 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;
}

Python KMP

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:

1. Edge case handling:

   • If t is empty, return 0
   • If t is longer than s, return -1

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

3. Character matching:

   • Use a nested loop to compare s[i + j] with t[j]
   • If all characters match, return i

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

Related Problems

• 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