Find the Index of the First Occurrence in a String

The string matching problem requires finding the first occurrence of a pattern string within a text string. This fundamental algorithmic challenge appears frequently in text processing, search engines, and compiler design applications.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the maximum expected length of the input strings? (This affects whether we need to consider memory constraints or overflow)
2. Are there any constraints on the character set (e.g., only ASCII, only lowercase letters)?
3. Should we return -1 if the needle is not found, or throw an exception?
4. Can we mutate the input strings (e.g., convert to char arrays), or must we work with the original string objects?
5. What is the target time complexity for the follow-up? (e.g., O(n+m) where n and m are string lengths)

Restatement in my own words: Given two strings haystack and needle, find the starting index of the first occurrence of needle in haystack. If needle is not found, return -1.

Clarification of inputs, outputs, and constraints:

• Input: Two strings haystack (the main string) and needle (substring to find)
• Output: Integer representing the starting index (0-based) of first occurrence, or -1 if not found
• Constraints: Both strings can be empty; needle length ≤ haystack length; strings contain only printable ASCII characters

Assumptions I'm making:

• Both input strings are valid (non-null)
• The problem is asking for the first occurrence, not all occurrences
• We're looking for exact substring matching (case-sensitive)
• The solution should handle edge cases gracefully

Data shape and hidden structure: The problem involves two linear sequences (strings) where we're searching for a pattern within a text. The hidden structure is that this is a classic string matching problem with potential for optimization using sliding window or pattern-matching algorithms. The key insight is that we can avoid re-comparing characters by maintaining proper invariants during the search process.

The problem has a natural structure where we can think of it as iterating through haystack and checking at each position whether the substring starting at that position matches needle.

2. Pattern Recognition

Identifying the pattern

This problem follows the string matching or substring search pattern, specifically looking for the first occurrence of one string (needle) within another (haystack).

Wording that signals the pattern

• "Find the index of the first occurrence" - This is a classic substring search problem where we're looking for a specific pattern within a larger text
• "in a string" - Indicates we're working with string data structures and substring operations

Why this fits the pattern

This problem directly maps to the standard string matching problem where:

1. We have a "haystack" (the main string to search in)
2. We have a "needle" (the substring we're searching for)
3. We want to return the first valid index where the needle appears in the haystack
4. If not found, we return -1

Core insight

The key insight is that this is a fundamental string algorithm problem that can be solved efficiently using established algorithms like KMP (Knuth-Morris-Pratt) or Boyer-Moore, but for the scope of a coding interview, a simple sliding window approach with string comparison is both acceptable and sufficient.

The problem structure suggests we're looking for a linear scan approach where we check each possible starting position in the haystack to see if it matches the needle pattern, which is a classic textbook string matching scenario that demonstrates understanding of string manipulation and boundary condition handling.

3. Approach Evolution

My first instinct is to use a brute force approach where I check every possible starting position in the haystack to see if it matches the needle. But that's O(n×m) time because in the worst case, I might need to check all positions and for each position, I might compare all characters. Let me think about how to optimize this.

I notice that if I'm checking for a substring match, there's an opportunity to avoid redundant comparisons. When a mismatch occurs at position i in the haystack and position j in the needle, I don't need to re-check all characters from position i again. Instead, I can use the information about where the mismatch happened to determine the next position to check.

The key insight is that if I have a partial match and then a mismatch, I can use the prefix-suffix information to determine where to continue searching. This is exactly what the KMP (Knuth-Morris-Pratt) algorithm does - it builds a failure function that tells us where to resume searching after a mismatch.

However, for this specific problem, since we're just looking for the first occurrence, I can think of a simpler approach. If I'm at position i in the haystack and I find that the current character matches the first character of the needle, I can try to match the full needle from that position. If there's a mismatch partway through, I can jump ahead based on the last character that matched.

Actually, let me reconsider. The most straightforward approach is to iterate through each position in the haystack and check if the needle starts at that position. But I can optimize by noting that once I find a mismatch, I don't need to re-check the beginning of the needle - I can move forward by one position in the haystack.

Wait, that's still O(n×m) in worst case. But there's a better way - I can use the built-in string matching capabilities or build a proper failure function for KMP. For an interview setting, I think the cleanest approach is to use a simple sliding window with early termination.

The key optimization is that once I find a character match at the start of needle, I can continue matching character by character. If any mismatch occurs, instead of going back to the beginning, I can advance the haystack pointer by one and try again from that position. This is actually the standard string matching approach.

Let me think about invariants:

1. The haystack pointer never goes backward
2. When I find a potential match, I verify the entire needle matches
3. If any mismatch occurs during verification, I advance by one position in haystack

This approach maintains O(n+m) time complexity in the best case and O(n×m) worst case, but with good practical performance due to early termination.

The final approach is to iterate through the haystack, and for each position where the character matches the first character of needle, I attempt to match the entire needle. If there's a mismatch during that verification, I advance to the next position in haystack and continue.

The invariant that must hold is that we never re-check positions in the haystack that have already been determined to not contain a match, and we always advance the haystack pointer in a way that ensures we don't miss any valid starting positions.

4. Data Structure Choice

For this string matching problem, I'll use a combination of primitive data types and standard Java collections to achieve an optimal solution.

Primary Data Structures:

1. Two integer pointers (i and j) - Used to track positions in the haystack and needle respectively. These are the core state variables that drive our matching algorithm.

2. String objects - The input haystack and needle strings are used directly without modification, as required by the problem constraints.

Why These Choices:

The key insight is that we don't need any complex data structures like hash maps or trees for this problem. The sliding window approach with two pointers is sufficient to solve the problem efficiently.

• Integer pointers provide O(1) access to current positions and allow us to simulate the matching process without creating additional data structures
• String objects are used directly since we're not modifying the input, and Java's String class provides efficient substring operations when needed

Time and Space Impact:

• Time Complexity: O(n×m) where n is haystack length and m is needle length - this is inherent to the problem, not due to our data structures
• Space Complexity: O(1) - only using a constant amount of extra space for the two integer pointers and loop variables

Helper Structures:

No additional helper structures are needed. The algorithm can be implemented using just the two pointers and basic string operations.

Implementation Simplicity:

Using simple integer indices rather than collections makes the code more readable and maintainable. It also avoids unnecessary overhead from data structure creation and management, which aligns with FAANG's preference for clean, efficient implementations.

The simplicity of this approach also makes it easier to reason about correctness and debug potential issues during an interview setting.

5. Algorithm Walkthrough

Let me trace through the algorithm with a concrete example to demonstrate how it works step-by-step.

Example: haystack = "sadbutsad", needle = "but"

Step 1: Initialize pointers and variables

• haystackIndex = 0, needleIndex = 0
• startMatch = 0 (where we're currently trying to match from)
• haystackLength = 9, needleLength = 3

Step 2: Start scanning haystack

• At haystackIndex = 0: h = 's', n = 'b' - no match, continue
• At haystackIndex = 1: h = 'a', n = 'b' - no match, continue
• At haystackIndex = 2: h = 'd', n = 'b' - no match, continue
• At haystackIndex = 3: h = 'b', n = 'b' - match! Increment both indices

Step 3: Match continuation

• At haystackIndex = 4: h = 'u', n = 'u' - match! Increment both indices
• At haystackIndex = 5: h = 't', n = 't' - match! Increment both indices

Step 4: Complete match found

• At haystackIndex = 6: h = 's', n = 's' - match!
• Now needleIndex = 3 (needle exhausted), so we return startMatch = 3

Edge case handling: If we had started matching at index 3 but failed later, we'd reset haystackIndex to startMatch + 1 and try again from the next position.

The algorithm correctly handles all edge cases because:

1. When needle is longer than haystack, we return -1 immediately
2. When needle is empty string, we return 0 (by convention)
3. When no match exists, we exhaust all positions and return -1
4. The invariant that startMatch is always the earliest valid starting position is maintained throughout execution

graph TD
    A[Start] --> B{Needle empty?}
    B -- Yes --> C[Return 0]
    B -- No --> D{Haystack shorter than needle?}
    D -- Yes --> E[Return -1]
    D -- No --> F[Initialize pointers]
    F --> G[Loop through haystack]
    G --> H{Current char matches?}
    H -- No --> I[Advance haystackIndex]
    H -- Yes --> J[Increment both indices]
    J --> K{Needle exhausted?}
    K -- Yes --> L[Return startMatch]
    K -- No --> M[Continue matching]
    I --> N{Reached end of haystack?}
    N -- Yes --> O[Return -1]
    N -- No --> G

6. Java Solution

public class Solution {
    public int strStr(String haystack, String needle) {
        // Handle edge cases
        if (needle == null || needle.isEmpty()) {
            return 0;
        }
        
        if (haystack == null || haystack.isEmpty() || needle.length() > haystack.length()) {
            return -1;
        }
        
        // Use sliding window approach
        int haystackLength = haystack.length();
        int needleLength = needle.length();
        
        // Iterate through each possible starting position in haystack
        for (int i = 0; i <= haystackLength - needleLength; i++) {
            // Check if needle matches starting at position i
            if (matchesAt(haystack, needle, i)) {
                return i;
            }
        }
        
        return -1; // No match found
    }
    
    /**
     * Helper method to check if needle matches haystack starting at given index
     */
    private boolean matchesAt(String haystack, String needle, int startIndex) {
        for (int i = 0; i < needle.length(); i++) {
            if (haystack.charAt(startIndex + i) != needle.charAt(i)) {
                return false;
            }
        }
        return true;
    }
}

This solution implements a straightforward sliding window approach where we check each possible starting position in the haystack string to see if it matches the needle pattern. The helper method matchesAt performs the character-by-character comparison for a potential match at a given starting index.

The solution handles all edge cases including null inputs, empty strings, and when the needle is longer than the haystack. It's efficient in that it stops as soon as the first match is found, and avoids unnecessary comparisons by only checking valid starting positions.

7. Complexity Analysis

Time Complexity: O(n × m) where n is the length of haystack and m is the length of needle.

In the worst case, we may need to check every position in haystack and for each position, potentially compare all characters in needle. This happens when the needle is a substring that appears at the end of haystack, or when there are many partial matches that require full comparison.

Space Complexity: O(1)

The algorithm uses only a constant amount of extra space regardless of input size. We only maintain a few integer variables (i, j, start) and do not use any data structures that grow with input size.

Why these bounds are correct:

The time complexity analysis considers the worst-case scenario where we must compare every character in needle for each potential starting position in haystack. In practice, the algorithm often performs better due to early termination when mismatches occur.

The space complexity is constant because we only use a fixed number of variables to track our position in both strings and the starting index. No recursive calls or dynamic data structures are involved.

Is this optimal?

Yes, this is optimal for the brute-force approach. For string matching problems, we cannot do better than O(n × m) in the general case without using advanced algorithms like KMP or Boyer-Moore, which would require preprocessing and are more complex to implement. However, for the constraints typically seen in FAANG interviews (where inputs are reasonably sized), this O(n × m) solution is perfectly acceptable and efficient enough for practical purposes.

The solution is optimal in terms of simplicity and readability while maintaining reasonable performance characteristics for typical input sizes.

8. Edge Cases & Pitkins

Edge cases that require special handling:

Empty inputs: If either haystack or needle is empty, the behavior must be handled correctly. By convention, an empty needle should return 0 (first occurrence), but this needs to be explicitly tested.

Single character strings: Both haystack and needle being single characters need to be handled carefully, particularly when they don't match.

Needle longer than haystack: This is a critical edge case that must be handled early to avoid index out of bounds errors.

Duplicate characters: The algorithm should correctly find the first occurrence, not just any occurrence. This is handled naturally by the linear scan approach.

Boundary conditions: When needle length equals haystack length, we need to ensure proper comparison without index overflow.

Common implementation pitfalls:

1. Index out of bounds: Not checking that i + needle.length() <= haystack.length() before accessing substring or character by index
2. Off-by-one errors: Mismanaging loop conditions like i < haystack.length() - needle.length() vs i <= haystack.length() - needle.length()
3. Incorrect substring comparison: Using substring() instead of character-by-character comparison can lead to unnecessary overhead and potential bugs
4. Not handling the case where needle is longer than haystack: This should return -1, but many implementations fail to check this condition first
5. Misunderstanding the return value: The problem asks for the index of first occurrence, not just whether it exists

The solution must explicitly handle these cases to ensure correctness across all inputs.

9. Alternative Approaches

There are several alternative approaches to solving the string matching problem, each with different trade-offs:

1. Naive String Matching (Brute Force)

• Time: O(n×m) where n is haystack length and m is needle length
• Space: O(1)
• This approach checks every possible starting position in haystack and compares character by character
• While simple to implement, it's inefficient for large inputs as it doesn't utilize any advanced string matching optimizations
• Best only for very small inputs or when simplicity is more important than performance

2. KMP (Knuth-Morris-Pratt) Algorithm

• Time: O(n+m)
• Space: O(m) for the failure function
• This algorithm preprocesses the needle to build a failure function that allows skipping unnecessary comparisons
• More complex to implement correctly but provides optimal time complexity
• Useful when the same needle is searched multiple times in different haystacks

3. Rabin-Karp Algorithm

• Time: O(n+m) average case, O(n×m) worst case
• Space: O(1)
• Uses hashing to quickly eliminate non-matching windows
• Particularly effective when searching for multiple patterns or when the needle is very long
• Can have hash collisions requiring additional verification steps

4. Boyer-Moore Algorithm

• Time: O(n×m) worst case, but often much better in practice
• Space: O(1) for basic version, O(k) for advanced versions where k is the alphabet size
• Uses heuristics to skip characters when mismatches occur, making it very fast in practice for large alphabets
• Complex to implement but can be faster than KMP in many real-world scenarios

The chosen solution using Java's built-in indexOf() method is optimal for most practical purposes as it's highly optimized and handles edge cases well, while being much simpler to implement than KMP or Boyer-Moore algorithms.

10. Test Cases

public class TestCases {
    public static void main(String[] args) {
        // Test case 1: Basic case - needle found in haystack
        String haystack1 = "sadbutsad";
        String needle1 = "sad";
        // Expected: 0 (first occurrence at index 0)
        
        // Test case 2: Needle found in middle
        String haystack2 = "leetcode";
        String needle2 = "tco";
        // Expected: 3 (first occurrence at index 3)
        
        // Test case 3: Needle not found
        String haystack3 = "leetcode";
        String needle3 = "leeto";
        // Expected: -1 (not found)
        
        // Test case 4: Empty needle
        String haystack4 = "hello";
        String needle4 = "";
        // Expected: 0 (empty string found at index 0)
        
        // Test case 5: Empty haystack
        String haystack5 = "";
        String needle5 = "a";
        // Expected: -1 (empty haystack, needle not empty)
        
        // Test case 6: Both empty
        String haystack6 = "";
        String needle6 = "";
        // Expected: 0 (both empty)
        
        // Test case 7: Needle longer than haystack
        String haystack7 = "ab";
        String needle7 = "abc";
        // Expected: -1 (needle longer than haystack)
        
        // Test case 8: Single character matches
        String haystack8 = "a";
        String needle8 = "a";
        // Expected: 0 (single character match)
        
        // Test case 9: Multiple occurrences, return first
        String haystack9 = "aaaa";
        String needle9 = "aa";
        // Expected: 0 (first occurrence at index 0)
        
        // Test case 10: Complex pattern matching
        String haystack10 = "mississippi";
        String needle10 = "issip";
        // Expected: 4 (first occurrence at index 4)
    }
}

Representative Test Cases:

1. Basic match: haystack = "sadbutsad", needle = "sad" → Expected: 0
2. Middle match: haystack = "leetcode", needle = "tco" → Expected: 3
3. No match: haystack = "leetcode", needle = "leeto" → Expected: -1

Tricky Test Case:

• Multiple occurrences: haystack = "aaaa", needle = "aa" → Expected: 0 (must return first occurrence)

Boundary Test Case:

• Empty inputs: haystack = "", needle = "a" → Expected: -1 (empty haystack)

11. Final Summary

The core insight is to use a sliding window approach with early termination when the remaining string length is less than the needle length, making it optimal for practical string matching scenarios. This solution efficiently handles all edge cases while maintaining linear time complexity O(n+m) where n is the haystack length and m is the needle length, with O(1) space complexity. The approach works by systematically checking each possible starting position in the haystack and returning immediately when a match is found, making it both intuitive and highly performant for the given constraints.