Solving Implement strStr() in JavaScript: Step-by-Step Guide

Introduction to Implement strStr()

The strStr() problem is one of the most classic string matching challenges you'll encounter in coding interviews and algorithmic practice. Originally inspired by the C standard library function strstr(), the task is deceptively simple: given two strings, find the index of the first occurrence of the second string within the first. If the substring is not found, return -1. If the substring is empty, return 0.

While JavaScript already provides built-in methods like indexOf() and includes(), implementing this function manually forces you to understand the underlying mechanics of string comparison, sliding windows, and pattern matching. These concepts form the foundation for more advanced algorithms like Knuth-Morris-Pratt (KMP) and Boyer-Moore.

Why This Problem Matters

Understanding strStr() is important for several reasons. First, it teaches you how to think about nested iteration and boundary conditions carefully. Second, it introduces the concept of a sliding window, a technique used in countless problems involving arrays and strings. Third, it serves as a gateway to learning efficient string search algorithms that achieve better than O(n*m) time complexity.

In real-world applications, string searching is everywhere: text editors finding words, search engines indexing content, bioinformatics matching DNA sequences, and IDEs providing autocomplete suggestions. Mastering the fundamentals here prepares you for these more complex scenarios.

Problem Statement

Given two strings haystack and needle, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. If needle is an empty string, return 0.

Examples

• haystack = "hello", needle = "ll" → returns 2
• haystack = "aaaaa", needle = "bba" → returns -1
• haystack = "", needle = "" → returns 0
• haystack = "mississippi", needle = "issip" → returns 4

Approach 1: The Brute Force Solution

The most intuitive approach is to compare the needle against every possible starting position in the haystack. For each starting index i, we check whether the substring of haystack beginning at i matches the needle character by character.

The outer loop runs from index 0 to haystack.length - needle.length, because beyond that point there aren't enough characters left to contain the needle. The inner loop compares each character of the needle with the corresponding character in the haystack.

Implementation

function strStr(haystack, needle) {
  // Edge case: empty needle
  if (needle.length === 0) {
    return 0;
  }

  const n = haystack.length;
  const m = needle.length;

  // If haystack is shorter than needle, no match is possible
  if (n < m) {
    return -1;
  }

  // Iterate through each possible starting position
  for (let i = 0; i <= n - m; i++) {
    let j = 0;

    // Compare characters one by one
    while (j < m && haystack[i + j] === needle[j]) {
      j++;
    }

    // If we matched all characters of needle, return the starting index
    if (j === m) {
      return i;
    }
  }

  return -1;
}

// Test cases
console.log(strStr("hello", "ll"));        // 2
console.log(strStr("aaaaa", "bba"));       // -1
console.log(strStr("", ""));               // 0
console.log(strStr("mississippi", "issip")); // 4

Complexity Analysis

The time complexity of this brute force approach is O(n * m) in the worst case, where n is the length of the haystack and m is the length of the needle. This worst case occurs when the needle almost matches at many positions, such as searching for "aaaab" in "aaaaaaaaaa". The space complexity is O(1) since we only use a few variables.

Approach 2: Using Built-in Methods

In production code, you would typically use JavaScript's built-in indexOf() method, which is highly optimized and often implemented in native code. This approach is worth knowing because it demonstrates awareness of language features and practical efficiency.

function strStr(haystack, needle) {
  if (needle.length === 0) {
    return 0;
  }
  return haystack.indexOf(needle);
}

console.log(strStr("hello", "ll"));  // 2
console.log(strStr("world", "xyz")); // -1

While this is the most practical solution for real applications, interviewers typically ask you to implement the logic manually to assess your algorithmic thinking.

Approach 3: Sliding Window with Substring Comparison

Another readable approach uses JavaScript's substring() or slice() method to extract a window of characters from the haystack and compare it directly with the needle. This is cleaner than the character-by-character comparison but creates a new string at each iteration, which can be less efficient for very large inputs.

function strStr(haystack, needle) {
  if (needle.length === 0) {
    return 0;
  }

  const n = haystack.length;
  const m = needle.length;

  for (let i = 0; i <= n - m; i++) {
    // Extract a substring of length m and compare
    if (haystack.slice(i, i + m) === needle) {
      return i;
    }
  }

  return -1;
}

console.log(strStr("hello", "ll"));          // 2
console.log(strStr("mississippi", "issip")); // 4

This approach has the same O(n * m) time complexity, but the constant factors may differ because string slicing in JavaScript engines is often optimized. However, it does use O(m) extra space per iteration for the sliced substring.

Approach 4: Knuth-Morris-Pratt (KMP) Algorithm

For large inputs or scenarios where performance is critical, the KMP algorithm provides O(n + m) time complexity. The key insight is that when a mismatch occurs, we can use information about previously matched characters to skip unnecessary comparisons. This is achieved by precomputing a "longest prefix suffix" (LPS) array for the needle.

The LPS array tells us, for each position in the needle, the length of the longest proper prefix that is also a suffix. When a mismatch happens at position j in the needle, instead of restarting from j = 0, we jump to j = lps[j - 1].

Building the LPS Array

function buildLPS(needle) {
  const lps = new Array(needle.length).fill(0);
  let len = 0; // Length of the previous longest prefix suffix
  let i = 1;

  while (i < needle.length) {
    if (needle[i] === needle[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        // Fall back in the LPS array
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }

  return lps;
}

Full KMP Implementation

function strStr(haystack, needle) {
  if (needle.length === 0) {
    return 0;
  }

  if (haystack.length < needle.length) {
    return -1;
  }

  const lps = buildLPS(needle);
  let i = 0; // Index for haystack
  let j = 0; // Index for needle

  while (i < haystack.length) {
    if (haystack[i] === needle[j]) {
      i++;
      j++;

      if (j === needle.length) {
        // Found a complete match
        return i - j;
      }
    } else {
      if (j !== 0) {
        // Use LPS to skip comparisons
        j = lps[j - 1];
      } else {
        i++;
      }
    }
  }

  return -1;
}

function buildLPS(needle) {
  const lps = new Array(needle.length).fill(0);
  let len = 0;
  let i = 1;

  while (i < needle.length) {
    if (needle[i] === needle[len]) {
      len++;
      lps[i] = len;
      i++;
    } else {
      if (len !== 0) {
        len = lps[len - 1];
      } else {
        lps[i] = 0;
        i++;
      }
    }
  }

  return lps;
}

// Test cases
console.log(strStr("hello", "ll"));           // 2
console.log(strStr("aaaaa", "bba"));          // -1
console.log(strStr("mississippi", "issip"));  // 4
console.log(strStr("ababcabcabababd", "ababd")); // 10

Complexity Analysis of KMP

The KMP algorithm runs in O(n + m) time: O(m) to build the LPS array and O(n) to search the haystack. The space complexity is O(m) for storing the LPS array. This makes it significantly faster than brute force for inputs with many partial matches.

Best Practices

• Handle edge cases first: Always check for an empty needle and cases where the haystack is shorter than the needle before entering any loops. This prevents unnecessary computation and potential bugs.
• Choose the right approach for the context: Use indexOf() in production code for reliability and speed. Use brute force in interviews when asked for a simple solution. Use KMP when you need guaranteed linear time performance.
• Avoid creating unnecessary substrings: The character-by-character comparison approach is more memory efficient than slicing substrings, especially for large inputs.
• Use descriptive variable names: Names like haystack and needle are clearer than s1 and s2. Similarly, use i and j consistently for outer and inner loop indices.
• Test with tricky inputs: Always test with overlapping patterns (like searching "aaa" in "aaaaa"), single-character strings, and cases where the needle appears at the very beginning or end of the haystack.
• Understand the trade-offs: KMP is faster asymptotically but has more overhead for small inputs. For short strings, brute force may actually be faster due to lower constant factors and better cache locality.

Common Pitfalls

One frequent mistake is setting the outer loop boundary incorrectly. Using i < haystack.length instead of i <= haystack.length - needle.length can cause you to miss matches near the end of the string or lead to out-of-bounds access. Another common error is forgetting to handle the empty needle case, which should return 0 by convention.

When implementing KMP, a subtle bug arises when updating the len variable in the LPS construction. Make sure you fall back using lps[len - 1] rather than resetting to zero, as resetting loses the prefix information that makes KMP efficient.

Conclusion

Implementing strStr() in JavaScript is an excellent exercise that builds your understanding of string manipulation, sliding windows, and pattern matching algorithms. The brute force approach offers a straightforward solution with O(n * m) complexity, while the KMP algorithm demonstrates how preprocessing can reduce the time complexity to O(n + m). By mastering both approaches, you gain the ability to choose the right tool for each situation, whether you are writing production code with built-in methods or tackling algorithmic challenges in technical interviews. Remember to always handle edge cases, test with diverse inputs, and consider the trade-offs between simplicity and performance when selecting your implementation strategy.