← Back to DevBytes
Developer Tutorial July 11, 2026 14 min read

Implement strStr(): Multiple Solutions and Complexity Analysis

What is strStr()?

The strStr() function, also known as "find substring in string" or "needle in haystack," is a fundamental string manipulation operation. Given two strings — a haystack (the main string to search within) and a needle (the substring to find) — the function returns the index of the first occurrence of the needle in the haystack. If the needle is not found, it returns -1. In many programming languages, this is equivalent to indexOf() in JavaScript, find() in Python, or strpos() in PHP.

The function signature typically looks like:

int strStr(string haystack, string needle)

Edge cases to consider:

Why Understanding strStr() Matters

🚀 Deploy your AI agent in 10 minutes

Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.

Try it free →

String searching is not just an academic exercise — it powers real-world functionality across countless domains:

Beyond practical utility, strStr() serves as an excellent gateway to understanding algorithm design trade-offs. The progression from a naive O(n·m) solution to sophisticated O(n+m) algorithms demonstrates how mathematical insight — like precomputation and state machines — can dramatically reduce computational cost. Mastering these techniques builds intuition for pattern matching, dynamic programming, and automata theory that transfers to more complex problems.

Solution 1: Naive Brute Force Approach

The simplest approach slides a window of length equal to the needle across the haystack, checking at each position whether the substring matches character by character.

Algorithm Steps

Complete Implementation

public int strStrNaive(String haystack, String needle) {
    // Edge case: empty needle
    if (needle.isEmpty()) {
        return 0;
    }
    
    int n = haystack.length();
    int m = needle.length();
    
    // Needle longer than haystack — impossible match
    if (m > n) {
        return -1;
    }
    
    // Slide window across haystack
    for (int i = 0; i <= n - m; i++) {
        int j;
        for (j = 0; j < m; j++) {
            if (haystack.charAt(i + j) != needle.charAt(j)) {
                break;  // Mismatch, move to next starting position
            }
        }
        // If we completed inner loop without breaking, full match found
        if (j == m) {
            return i;
        }
    }
    
    return -1;  // No match found
}

Complexity Analysis

The naive approach is acceptable for small strings or one-off searches, but it degrades badly on repetitive patterns. Its simplicity makes it a great baseline, but production scenarios demand better.

Solution 2: Knuth-Morris-Pratt (KMP) Algorithm

The KMP algorithm eliminates redundant comparisons by precomputing a Longest Prefix Suffix (LPS) table. When a mismatch occurs, instead of starting over from the next character, the algorithm uses the LPS table to skip ahead to a position where certain characters are already guaranteed to match.

Core Insight: The LPS Array

For a pattern string, the LPS value at index i represents the length of the longest proper prefix of the pattern that is also a suffix of the substring pattern[0..i]. This tells us how many characters we can safely skip when a mismatch happens.

For example, consider needle = "ababc":

Resulting LPS array: [0, 0, 1, 2, 0]

Building the LPS Table

private int[] buildLPS(String pattern) {
    int m = pattern.length();
    int[] lps = new int[m];
    
    int len = 0;  // Length of the current matching prefix
    int i = 1;    // Start from index 1 (lps[0] is always 0)
    
    while (i < m) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                // Fall back to previous prefix length
                len = lps[len - 1];
                // Do NOT increment i here — re-evaluate with new len
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
    
    return lps;
}

This construction runs in O(m) time. The key trick: when characters mismatch and len > 0, we set len = lps[len-1] and stay at the same i. This recursive fallback uses previously computed LPS values to avoid backtracking in the pattern itself.

KMP Search Implementation

public int strStrKMP(String haystack, String needle) {
    if (needle.isEmpty()) {
        return 0;
    }
    
    int n = haystack.length();
    int m = needle.length();
    
    if (m > n) {
        return -1;
    }
    
    // Precompute the LPS table
    int[] lps = buildLPS(needle);
    
    int i = 0;  // Index for haystack
    int j = 0;  // Index for needle
    
    while (i < n) {
        if (haystack.charAt(i) == needle.charAt(j)) {
            i++;
            j++;
            
            // Full match found
            if (j == m) {
                return i - j;  // Starting index of match
            }
        } else {
            if (j != 0) {
                // Use LPS to skip ahead — no need to restart from scratch
                j = lps[j - 1];
                // i stays the same, we'll re-compare with new j
            } else {
                // j is 0, just move haystack pointer forward
                i++;
            }
        }
    }
    
    return -1;
}

How KMP Avoids Redundant Work

Imagine haystack = "ababcabcab" and needle = "abcab". When a mismatch occurs at position 5 (haystack[5]='c' vs needle[5] doesn't exist since needle length is 5... let's use a clearer example):

Consider haystack = "aaaaab" and needle = "aaab". At i=0, we match "aaa" then hit 'a' vs 'b' at j=3. Instead of sliding to i=1 and re-comparing "aa" from scratch, KMP knows from LPS[2]=2 that the first two characters of the needle match the last two characters we just saw. It sets j=2 and continues comparing from haystack[3] vs needle[2], effectively skipping redundant checks.

Complexity Analysis

Solution 3: Rabin-Karp (Rolling Hash) Algorithm

Rabin-Karp takes a completely different approach: instead of comparing characters, it compares hash values. It computes a hash for the needle, then slides a window over the haystack, updating the hash in O(1) time at each step using a rolling hash technique. Only when hash values match does it perform an actual character-by-character comparison to rule out collisions.

The Rolling Hash Mechanism

A standard rolling hash uses a base B (typically 256 for ASCII, or a prime like 101) and a modulus M (a large prime to avoid overflow). The hash of a string of length m is:

hash(s) = (s[0]·B^(m-1) + s[1]·B^(m-2) + ... + s[m-1]·B^0) mod M

When sliding the window forward by one character, the old hash can be updated in constant time:

newHash = ((oldHash - oldChar·B^(m-1)) · B + newChar) mod M

Complete Rabin-Karp Implementation

public int strStrRabinKarp(String haystack, String needle) {
    if (needle.isEmpty()) {
        return 0;
    }
    
    int n = haystack.length();
    int m = needle.length();
    
    if (m > n) {
        return -1;
    }
    
    // Parameters for rolling hash
    final int BASE = 256;
    final int MOD = 1_000_000_007;  // Large prime to minimize collisions
    long basePow = 1;  // Will store BASE^(m-1) mod MOD
    
    // Compute BASE^(m-1) % MOD
    for (int i = 0; i < m - 1; i++) {
        basePow = (basePow * BASE) % MOD;
    }
    
    // Compute hash of needle
    long needleHash = 0;
    for (int i = 0; i < m; i++) {
        needleHash = (needleHash * BASE + needle.charAt(i)) % MOD;
    }
    
    // Compute hash of first window in haystack
    long windowHash = 0;
    for (int i = 0; i < m; i++) {
        windowHash = (windowHash * BASE + haystack.charAt(i)) % MOD;
    }
    
    // Slide the window
    for (int i = 0; i <= n - m; i++) {
        // Check hash match
        if (windowHash == needleHash) {
            // Verify character by character to rule out hash collision
            boolean match = true;
            for (int j = 0; j < m; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    match = false;
                    break;
                }
            }
            if (match) {
                return i;
            }
        }
        
        // Slide window: remove haystack[i] and add haystack[i+m]
        if (i < n - m) {
            // Remove contribution of outgoing character
            windowHash = (windowHash - haystack.charAt(i) * basePow % MOD + MOD) % MOD;
            // Shift left and add incoming character
            windowHash = (windowHash * BASE + haystack.charAt(i + m)) % MOD;
        }
    }
    
    return -1;
}

Handling Hash Collisions

Two different strings can produce the same hash value modulo M. This is why the code always performs a full string comparison when hashes match. In practice, with a well-chosen large prime modulus, collisions are extremely rare, and the algorithm behaves as if it's O(n+m) on average. However, an adversary could craft inputs that cause many collisions (e.g., by exploiting the specific modulus), degrading performance to O(n·m) in the worst case.

Complexity Analysis

Rabin-Karp shines when searching for multiple patterns simultaneously — you can compute hashes for many needles and check each window against all of them. This multi-pattern capability makes it popular in plagiarism detection and network filtering systems.

Solution 4: Boyer-Moore Algorithm (Overview)

Boyer-Moore is often the fastest algorithm in practice for large alphabets (like English text). It preprocesses the needle to create two heuristic tables and then compares from right to left, allowing it to skip large portions of the haystack.

Two Key Heuristics

Simplified Boyer-Moore Implementation (Bad Character Rule Only)

public int strStrBoyerMoore(String haystack, String needle) {
    if (needle.isEmpty()) {
        return 0;
    }
    
    int n = haystack.length();
    int m = needle.length();
    
    if (m > n) {
        return -1;
    }
    
    // Precompute last occurrence positions for each character in needle
    // For characters not in needle, store -1
    int[] last = new int[256];  // Assuming ASCII
    for (int i = 0; i < 256; i++) {
        last[i] = -1;
    }
    for (int i = 0; i < m; i++) {
        last[needle.charAt(i)] = i;
    }
    
    int i = 0;  // Haystack index where we attempt to align needle start
    
    while (i <= n - m) {
        int j = m - 1;  // Start comparing from the rightmost character
        
        // Compare from right to left
        while (j >= 0 && haystack.charAt(i + j) == needle.charAt(j)) {
            j--;
        }
        
        // If j < 0, we matched the entire needle
        if (j < 0) {
            return i;
        }
        
        // Mismatch at needle[j] with haystack[i+j]
        // Get last occurrence of the mismatched character in needle
        int lastOcc = last[haystack.charAt(i + j)];
        
        // Shift: align needle so that the mismatched char matches
        // If lastOcc < j, shift by j - lastOcc
        // If lastOcc > j (character appears later in needle), shift by 1
        // If lastOcc == -1 (character not in needle), shift past it entirely
        int shift = Math.max(1, j - lastOcc);
        i += shift;
    }
    
    return -1;
}

Complexity Analysis

Comparative Analysis Summary

Here's how the four solutions stack up against each other:

┌─────────────────┬──────────────────┬──────────────┬───────────────┬──────────────────────┐
│   Algorithm     │  Average Time    │  Worst Time  │    Space      │  Best For            │
├─────────────────┼──────────────────┼──────────────┼───────────────┼──────────────────────┤
│ Naive           │ O(n·m)           │ O(n·m)       │ O(1)          │ Small strings,       │
│                 │                  │              │               │ learning baseline    │
├─────────────────┼──────────────────┼──────────────┼───────────────┼──────────────────────┤
│ KMP             │ O(n + m)         │ O(n + m)     │ O(m)          │ Guaranteed linear,   │
│                 │                  │              │               │ repetitive patterns  │
├─────────────────┼──────────────────┼──────────────┼───────────────┼──────────────────────┤
│ Rabin-Karp      │ O(n + m)*        │ O(n·m)       │ O(1)          │ Multiple pattern     │
│                 │                  │              │               │ search simultaneously │
├─────────────────┼──────────────────┼──────────────┼───────────────┼──────────────────────┤
│ Boyer-Moore     │ O(n/m) best      │ O(n·m)       │ O(1) fixed    │ Large alphabets,     │
│                 │ O(n) average     │              │ alphabet      │ practical text search │
└─────────────────┴──────────────────┴──────────────┴───────────────┴──────────────────────┘

* Average case with low collision probability; degrades with adversarial inputs.

Best Practices for Choosing and Implementing strStr()

Match the Algorithm to Your Data

Implementation Tips

Testing Your Implementation

A robust test suite should include:

// Test cases to validate your strStr() implementation

// 1. Basic functionality
assert strStr("hello", "ll") == 2;
assert strStr("hello", "hello") == 0;
assert strStr("hello", "world") == -1;

// 2. Empty needle
assert strStr("anything", "") == 0;

// 3. Needle longer than haystack
assert strStr("short", "longer_needle") == -1;

// 4. Match at boundaries
assert strStr("abc", "a") == 0;
assert strStr("abc", "c") == 2;

// 5. Overlapping patterns
assert strStr("aaaaa", "aa") == 0;  // First occurrence
assert strStr("ababa", "aba") == 0; // Overlapping: occurs at 0 and 2

// 6. Repetitive pattern (stress test for naive approach)
String haystack = "a".repeat(100000) + "b";
String needle = "a".repeat(9999) + "b";
// Should return correct index without timing out

// 7. Case sensitivity
assert strStr("Hello", "hello") == -1;
assert strStr("Hello", "Hell") == 0;

Conclusion

Implementing strStr() opens a window into the rich landscape of string algorithm design. Starting from the straightforward naive sliding window, we've progressed through KMP's elegant LPS-based state machine that guarantees linear time, Rabin-Karp's hash-driven approach that generalizes beautifully to multi-pattern search, and Boyer-Moore's right-to-left scanning with heuristic skipping that dominates in practical text processing. Each algorithm represents a different philosophical approach: exhaustive comparison, precomputed automata, numeric fingerprinting, and rule-based jumping. The choice among them hinges on your input characteristics, performance requirements, and the number of patterns you need to find. By internalizing these techniques, you equip yourself not just to solve a LeetCode problem, but to make informed engineering decisions whenever pattern matching appears — and in software, it appears everywhere.

🚀 Need a reliable AI agent for your project?

Deploy Hermes Agent in 10 minutes. Managed hosting, zero DevOps.

Get Started — $23.99/mo
← Back to all articles