Multiple Approaches to Find the Nth Occurrence of a Substring in Java

Problem Context and Requirements Analysis

In string processing, locating specific substring occurrences is a common requirement. While Java's standard library provides the indexOf() method for finding the first occurrence, specialized programming techniques are needed to locate the Nth occurrence.

Core Solution: Iterative Approach Using indexOf

Java's String.indexOf() method offers an overloaded version that allows specifying the search starting position. Leveraging this feature, we can implement Nth occurrence finding through iterative calls:

public static int findNthOccurrence(String str, String substring, int n) {
    int index = -1;
    for (int i = 0; i < n; i++) {
        index = str.indexOf(substring, index + 1);
        if (index == -1) {
            return -1;
        }
    }
    return index;
}

This method works by repeatedly calling indexOf(), each time starting the search from just after the previously found position, until the Nth occurrence is located. For the specific case of finding the second occurrence, this can be simplified to:

String str = "itiswhatitis";
String substring = "is";
int secondIndex = str.indexOf(substring, str.indexOf(substring) + 1);
System.out.println(secondIndex); // Output: 10

Recursive Implementation

The recursive approach provides an alternative implementation with clear logical structure:

public static int findNthOccurrenceRecursive(String str, String substring, int n) {
    if (n <= 0) {
        throw new IllegalArgumentException("n must be greater than 0");
    }
    
    if (n == 1) {
        return str.indexOf(substring);
    }
    
    int firstIndex = str.indexOf(substring);
    if (firstIndex == -1) {
        return -1;
    }
    
    String remaining = str.substring(firstIndex + substring.length());
    int nextIndex = findNthOccurrenceRecursive(remaining, substring, n - 1);
    
    return nextIndex == -1 ? -1 : firstIndex + substring.length() + nextIndex;
}

Third-Party Library Solution

Apache Commons Lang library provides the StringUtils.ordinalIndexOf() method for direct implementation:

import org.apache.commons.lang3.StringUtils;

String str = "itiswhatitis";
int secondIndex = StringUtils.ordinalIndexOf(str, "is", 2);
System.out.println(secondIndex); // Output: 10

This method encapsulates the search logic, offering simplicity and stable performance, making it ideal for projects already using this library.

Regular Expression Approach

For complex pattern matching requirements, Java's regex API can be utilized:

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public static int findNthOccurrenceRegex(String str, String pattern, int n) {
    Matcher matcher = Pattern.compile(Pattern.quote(pattern)).matcher(str);
    int count = 0;
    while (matcher.find()) {
        count++;
        if (count == n) {
            return matcher.start();
        }
    }
    return -1;
}

This approach is particularly suitable for scenarios requiring complex pattern matching rather than fixed string searches.

Performance Analysis and Selection Guidelines

Different methods offer distinct advantages in practical applications:

• Iterative indexOf approach: Best performance, minimal memory footprint, suitable for most scenarios
• Recursive method: Clear code structure but risks stack overflow, not recommended for long strings
• Apache Commons Lang: Easy to use but requires additional dependencies
• Regular expression: Powerful functionality but relatively lower performance, ideal for complex matching needs

Selection should be based on project requirements and performance considerations. For simple fixed substring searches, the iterative indexOf-based approach is recommended.