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

Introduction to strStr()

The strStr() problem is one of the most classic string matching challenges you'll encounter in coding interviews and algorithmic practice. Originally popularized by LeetCode, it asks you to implement a function that finds the first occurrence of a substring (the "needle") within another string (the "haystack") and returns its starting index. If the needle is not found, the function should return -1.

In Go, while the standard library provides strings.Index() to do exactly this, implementing it yourself is an excellent way to understand string manipulation, pointer arithmetic, and pattern matching algorithms. This tutorial walks you through multiple approaches, from the brute-force method to more optimized techniques, all written in idiomatic Go.

What Is strStr() and Why It Matters

The name strStr() comes from the C standard library function strstr(), which searches for a substring within a string. The problem statement is straightforward:

• Given two strings haystack and needle, return the index of the first occurrence of needle in haystack.
• If needle is an empty string, return 0 by convention.
• If needle is not found, return -1.

This problem matters for several reasons. First, it tests your ability to handle edge cases such as empty strings, strings longer than the haystack, and overlapping matches. Second, it serves as a gateway to more advanced string matching algorithms like the Knuth-Morris-Pratt (KMP) algorithm, the Boyer-Moore algorithm, and the Rabin-Karp algorithm. Finally, understanding substring search is foundational for building features like search bars, text editors, and bioinformatics tools.

Setting Up the Problem in Go

Before diving into solutions, let's define the function signature we'll be working with. In Go, strings are immutable sequences of bytes, but for most substring problems, we can treat them as sequences of characters as long as we're working with ASCII or we're careful about Unicode.

package main

import "fmt"

// strStr returns the index of the first occurrence of needle in haystack,
// or -1 if needle is not part of haystack.
func strStr(haystack string, needle string) int {
    // Implementation goes here
    return -1
}

func main() {
    fmt.Println(strStr("hello", "ll"))      // Expected: 2
    fmt.Println(strStr("aaaaa", "bba"))     // Expected: -1
    fmt.Println(strStr("", ""))             // Expected: 0
}

Now let's build out the implementation step by step.

Approach 1: Brute Force Sliding Window

The most intuitive approach is to slide the needle across the haystack one position at a time, comparing characters at each position. If all characters match, we return the starting index. If we reach the end of the haystack without a match, we return -1.

Handling Edge Cases

Before implementing the core logic, we need to handle edge cases. If the needle is empty, we return 0. If the needle is longer than the haystack, it's impossible to find a match, so we return -1.

func strStr(haystack string, needle string) int {
    if len(needle) == 0 {
        return 0
    }
    if len(needle) > len(haystack) {
        return -1
    }

    // We only need to check positions where the needle can fully fit
    for i := 0; i <= len(haystack)-len(needle); i++ {
        match := true
        for j := 0; j < len(needle); j++ {
            if haystack[i+j] != needle[j] {
                match = false
                break
            }
        }
        if match {
            return i
        }
    }
    return -1
}

Complexity Analysis

The brute force approach has a time complexity of O(n * m) where n is the length of the haystack and m is the length of the needle. In the worst case, such as searching for "aaaaab" in "aaaaaaaaaa", we compare nearly every character of the needle at nearly every position. The space complexity is O(1) since we only use a few variables.

For most practical inputs, this approach is perfectly acceptable. However, for very large strings or repeated searches, more efficient algorithms are worth exploring.

Approach 2: Using Go's String Slicing

Go's string slicing provides a clean way to compare substrings directly. Instead of comparing character by character, we can extract a slice of the haystack that matches the needle's length and compare it directly to the needle.

func strStr(haystack string, needle string) int {
    if len(needle) == 0 {
        return 0
    }
    if len(needle) > len(haystack) {
        return -1
    }

    for i := 0; i <= len(haystack)-len(needle); i++ {
        if haystack[i:i+len(needle)] == needle {
            return i
        }
    }
    return -1
}

This version is more concise and arguably more readable. Under the hood, Go's string comparison still compares bytes, so the time complexity remains O(n * m). However, the comparison is implemented in optimized assembly on most platforms, so this version often performs better in practice than the manual character-by-character loop.

Approach 3: The Knuth-Morris-Pratt (KMP) Algorithm

The KMP algorithm improves on brute force by avoiding redundant comparisons. When a mismatch occurs, KMP uses a precomputed "partial match" table (also called the failure function) to skip ahead intelligently. The key insight is that when a partial match fails, we already know some characters matched, and we can use that information to determine where to resume searching.

Building the LPS Array

The Longest Proper Prefix which is also Suffix (LPS) array tells us, for each position in the needle, the length of the longest proper prefix of the needle that is also a suffix of the substring ending at that position. This array allows us to skip comparisons we know will fail.

func computeLPS(needle string) []int {
    lps := make([]int, len(needle))
    length := 0 // Length of the previous longest prefix suffix
    i := 1

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

Implementing KMP Search

With the LPS array in hand, the search itself becomes more efficient. When a mismatch occurs, instead of moving back to the start of the needle, we use the LPS array to determine how far we can skip ahead.

func strStrKMP(haystack string, needle string) int {
    if len(needle) == 0 {
        return 0
    }
    if len(needle) > len(haystack) {
        return -1
    }

    lps := computeLPS(needle)
    i := 0 // Index for haystack
    j := 0 // Index for needle

    for i < len(haystack) {
        if haystack[i] == needle[j] {
            i++
            j++
        }
        if j == len(needle) {
            return i - j
        } else if i < len(haystack) && haystack[i] != needle[j] {
            if j != 0 {
                j = lps[j-1]
            } else {
                i++
            }
        }
    }
    return -1
}

The KMP algorithm runs in O(n + m) time, where n is the length of the haystack and m is the length of the needle. The LPS array takes O(m) space. This makes KMP significantly faster than brute force for inputs with many partial matches.

Approach 4: Rabin-Karp With Rolling Hash

The Rabin-Karp algorithm uses hashing to compare substrings. Instead of comparing characters directly, it computes a hash of the needle and compares it to the hash of each window in the haystack. The clever part is the "rolling" hash, which allows computing the hash of the next window in constant time from the hash of the current window.

func strStrRabinKarp(haystack string, needle string) int {
    if len(needle) == 0 {
        return 0
    }
    if len(needle) > len(haystack) {
        return -1
    }

    const base = 256
    const mod = 101 // A prime number to reduce collisions

    nLen := len(needle)
    hLen := len(haystack)

    // Compute hash of needle and first window of haystack
    needleHash := 0
    windowHash := 0
    h := 1 // The value of base^(nLen-1) % mod

    for i := 0; i < nLen-1; i++ {
        h = (h * base) % mod
    }

    for i := 0; i < nLen; i++ {
        needleHash = (base*needleHash + int(needle[i])) % mod
        windowHash = (base*windowHash + int(haystack[i])) % mod
    }

    // Slide the window over the haystack
    for i := 0; i <= hLen-nLen; i++ {
        if needleHash == windowHash {
            // Verify character by character to handle hash collisions
            match := true
            for j := 0; j < nLen; j++ {
                if haystack[i+j] != needle[j] {
                    match = false
                    break
                }
            }
            if match {
                return i
            }
        }

        // Compute hash for the next window
        if i < hLen-nLen {
            windowHash = (base*(windowHash-int(haystack[i])*h) + int(haystack[i+nLen])) % mod
            if windowHash < 0 {
                windowHash += mod
            }
        }
    }
    return -1
}

The average time complexity of Rabin-Karp is O(n + m), but the worst case is O(n * m) due to hash collisions. In practice, with a good hash function and a prime modulus, collisions are rare and the algorithm performs well.

Comparing the Approaches

Each approach has trade-offs that make it suitable for different scenarios:

• Brute Force: Simple to implement and understand. Best for short strings or one-off searches where code clarity matters more than performance.
• String Slicing: Leverages Go's optimized built-in comparison. Often the fastest in practice for moderate input sizes due to assembly-optimized byte comparison.
• KMP: Guaranteed linear time. Ideal for large inputs or when you need predictable performance, especially with repetitive patterns.
• Rabin-Karp: Useful when you need to search for multiple patterns simultaneously, since you can precompute hashes for all patterns and compare in a single pass.

Best Practices

When implementing strStr() or any substring search in Go, keep these best practices in mind:

• Always handle edge cases first: Empty needles, needles longer than the haystack, and empty haystacks should be checked before entering the main loop. This prevents unnecessary computation and potential panics.
• Use the standard library when appropriate: Go's strings.Index() is highly optimized and battle-tested. Unless you're practicing algorithms or have a specific need, prefer it over a custom implementation.
• Be careful with Unicode: Go strings are byte sequences. If your input contains multi-byte UTF-8 characters, indexing by byte position may split a character. For Unicode-aware searching, convert strings to []rune first.
• Benchmark before optimizing: The brute force or slicing approach is often fast enough. Use Go's built-in benchmarking tools (testing.B) to measure before reaching for KMP or Rabin-Karp.
• Write table-driven tests: Cover cases like empty strings, single-character needles, needles at the start, middle, and end of the haystack, no-match scenarios, and overlapping patterns.

Example Table-Driven Test

package main

import "testing"

func TestStrStr(t *testing.T) {
    tests := []struct {
        haystack string
        needle   string
        expected int
    }{
        {"hello", "ll", 2},
        {"aaaaa", "bba", -1},
        {"", "", 0},
        {"abc", "", 0},
        {"abc", "abcd", -1},
        {"mississippi", "issip", 4},
        {"aaaabaaaab", "aaaaa", 5},
        {"a", "a", 0},
        {"abc", "c", 2},
    }

    for _, tt := range tests {
        result := strStr(tt.haystack, tt.needle)
        if result != tt.expected {
            t.Errorf("strStr(%q, %q) = %d; expected %d",
                tt.haystack, tt.needle, result, tt.expected)
        }
    }
}

Unicode Considerations

If your application deals with international text, you need to account for multi-byte characters. Consider the string "héllo" where the character 'é' is two bytes in UTF-8. A naive byte-level search for "ll" would still work, but indexing and slicing become tricky if you need to return a character index rather than a byte index.

func strStrRune(haystack string, needle string) int {
    if needle == "" {
        return 0
    }

    hRunes := []rune(haystack)
    nRunes := []rune(needle)

    if len(nRunes) > len(hRunes) {
        return -1
    }

    for i := 0; i <= len(hRunes)-len(nRunes); i++ {
        match := true
        for j := 0; j < len(nRunes); j++ {
            if hRunes[i+j] != nRunes[j] {
                match = false
                break
            }
        }
        if match {
            return i
        }
    }
    return -1
}

This version returns the character index rather than the byte index, which is more intuitive for human-readable text. The trade-off is the O(n) space needed to convert strings to rune slices.

Conclusion

Implementing strStr() in Go is a rewarding exercise that teaches fundamental string manipulation techniques and introduces you to classic pattern matching algorithms. The brute force and slicing approaches are perfect for most everyday use cases, offering simplicity and leveraging Go's optimized runtime. For scenarios demanding guaranteed linear performance, KMP provides an elegant solution with its LPS array, while Rabin-Karp shines when searching for multiple patterns simultaneously. By understanding all four approaches, you'll be well-equipped to choose the right tool for any substring search problem, whether you're tackling a coding interview or building production software. Remember to always handle edge cases, consider Unicode implications, and benchmark your implementation before reaching for complex optimizations.