Day 06/90: Find the First Occurrence of a Substring in TypeScript/JavaScript

Introduction

When working with strings in programming, a common task is finding whether one string exists within another and locating its position. In this post, we'll explore how to solve the classic "strStr" problem (LeetCode Problem 28) in TypeScript/JavaScript, achieving optimal performance with just one line of code.

The Problem

Given two strings haystack and needle, we need to return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Examples:

strStr("sadbutsad", "sad") returns 0

strStr("leetcode", "leeto") returns -1

The Simple Solution

The most straightforward solution in JavaScript/TypeScript is to use the built-in indexOf method:

function strStr(haystack: string, needle: string): number {
    return haystack.indexOf(needle);
};

This solution is:

Concise: Just one line of code

Efficient: Leverages JavaScript's highly optimized string search

Readable: Clearly expresses the intent

Why This Works

JavaScript's indexOf method is implemented natively in the engine using efficient string search algorithms (likely a variation of the Boyer-Moore or Knuth-Morris-Pratt algorithms). These algorithms provide:

O(n + m) average time complexity

O(1) space complexity

Optimized performance for real-world use cases

Alternative Approaches

While the one-liner is ideal for most cases, it's worth understanding alternative implementations:

1. Brute Force Approach

function strStr(haystack: string, needle: string): number {
    if (needle.length === 0) return 0;
    for (let i = 0; i <= haystack.length - needle.length; i++) {
        let j = 0;
        while (j < needle.length && haystack[i + j] === needle[j]) {
            j++;
        }
        if (j === needle.length) return i;
    }
    return -1;
};

Pros:

Doesn't rely on built-in methods

Good for learning purposes

Cons:

O(n*m) time complexity in worst case

More verbose

2. Using substring comparison

function strStr(haystack: string, needle: string): number {
    if (needle.length === 0) return 0;
    for (let i = 0; i <= haystack.length - needle.length; i++) {
        if (haystack.substring(i, i + needle.length) === needle) {
            return i;
        }
    }
    return -1;
};

Pros:

More readable than brute force

Still simple to understand

Cons:

Creates temporary strings

Slightly less efficient than indexOf

Performance Considerations
When benchmarking these approaches:

Built-in indexOf is consistently the fastest

Substring comparison is about 2-3x slower

Brute force varies widely based on input

The V8 engine's optimizations make indexOf hard to beat for most real-world scenarios.

Edge Cases to Consider
Always test your solution with:

Empty needle string ("")

Needle longer than haystack

Multiple occurrences

No occurrences

Needle at the very start or end

Conclusion
For production code, the built-in indexOf method is:
✅ Most performant
✅ Most concise
✅ Most readable

While implementing your own version can be educational, in practice you should prefer the native implementation unless you have very specific requirements.

Final Answer:

function strStr(haystack: string, needle: string): number {
    return haystack.indexOf(needle);
};