Shortest Matching Substring

Hard

#3071Time: O(N*M), where N is `s.length()` and M is `p.length()`. The `startsWith` calls inside loops lead to this complexity. If we pre-calculate all occurrences using an efficient algorithm like KMP, the complexity becomes O(N + M).Space: O(N), where N is the length of `s`. This is for the two auxiliary arrays `latestStart` and `earliestEnd`.

Patterns

Two Pointers String Matching

Algorithms

Binary Search

Data structures

String

Prompt

You are given a string s and a pattern string p, where p contains exactly two '*' characters.

The '*' in p matches any sequence of zero or more characters.

Return the length of the shortest substring in s that matches p. If there is no such substring, return -1.

Note: The empty substring is considered valid.

Example 1:

Input: s = "abaacbaecebce", p = "ba*c*ce"

Output: 8

Explanation:

The shortest matching substring of p in s is "baecebce".

Example 2:

Input: s = "baccbaadbc", p = "cc*baa*adb"

Output: -1

Explanation:

There is no matching substring in s.

Example 3:

Input: s = "a", p = "**"

Output: 0

Explanation:

The empty substring is the shortest matching substring.

Example 4:

Input: s = "madlogic", p = "*adlogi*"

Output: 6

Explanation:

The shortest matching substring of p in s is "adlogi".

Constraints:

1 <= s.length <= 10⁵
2 <= p.length <= 10⁵
s contains only lowercase English letters.
p contains only lowercase English letters and exactly two '*'.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach achieves optimal linear time complexity by replacing the binary searches of the previous method with precomputed lookup tables. By investing in a linear-time preprocessing step to build these tables, we can find the best corresponding part1 and part3 for each potential part2 in constant time.

Algorithm

Parse and Find Occurrences: As in the previous approach, parse p into part1, part2, part3. Find all occurrences of part2 and store them in a list middles.
Precomputation for part1: Create an array latestStart of size N (length of s). latestStart[i] will store the starting index of the latest occurrence of part1 that begins at or before index i. This array can be filled in O(N) with a single pass.
Precomputation for part3: Create an array earliestEnd of size N+1. earliestEnd[i] will store the starting index of the earliest occurrence of part3 that begins at or after index i. This array can be filled in O(N) with a single pass backwards.
Combining: Iterate through each middleIdx from the middles list.
1. For each middleIdx, the latest part1 must start at or before middleIdx - part1.length(). We can find its starting position i by a direct O(1) lookup in our precomputed array: i = latestStart[middleIdx - part1.length()].
2. Similarly, the earliest part3 must start at or after middleIdx + part2.length(). We find its starting position l with an O(1) lookup: l = earliestEnd[middleIdx + part2.length()].
3. If both i and l are valid, we have found a match. Calculate its length (l + part3.length()) - i and update the minimum length.
Handle Empty part2: If part2 is empty, the middles list will be empty. In this case, we must iterate through all possible split points i from 0 to N in s, treating i as the boundary between part1 and part3, and use the precomputed arrays to find the best match.

Walkthrough

The key insight for optimization is that for every occurrence of part2, we always ask the same questions: what is the latest valid part1 before it, and what is the earliest valid part3 after it? These questions can be pre-answered for all possible positions in s.

We create two arrays:

latestStart[i]: Stores the starting index of the latest part1 that starts at or before index i.
earliestEnd[i]: Stores the starting index of the earliest part3 that starts at or after index i.

These arrays act as lookup tables. latestStart is built by iterating forward through s, and earliestEnd is built by iterating backward. Once these tables are ready, we can iterate through each occurrence of part2 at middleIdx and find the optimal startIdx and endIdx in O(1) time, leading to an overall linear time solution.

1import java.util.ArrayList;2import java.util.Arrays;3import java.util.List;4 5class Solution {6    public int shortestMatchingSubstring(String s, String p) {7        String[] parts = p.split("\\*", -1);8        String part1 = parts[0], part2 = parts[1], part3 = parts[2];9        int n = s.length();10 11        if (part1.isEmpty() && part2.isEmpty() && part3.isEmpty()) return 0;12 13        int[] latestStart = new int[n];14        Arrays.fill(latestStart, -1);15        int last = -1;16        for (int i = 0; i < n; i++) {17            if (s.startsWith(part1, i)) {18                last = i;19            }20            latestStart[i] = last;21        }22 23        int[] earliestEnd = new int[n + 1];24        Arrays.fill(earliestEnd, -1);25        last = -1;26        for (int i = n - 1; i >= 0; i--) {27            if (s.startsWith(part3, i)) {28                last = i;29            }30            earliestEnd[i] = last;31        }32        for (int i = n - 2; i >= 0; i--) {33            if (earliestEnd[i] == -1) {34                earliestEnd[i] = earliestEnd[i + 1];35            }36        }37 38        long minLength = Long.MAX_VALUE;39 40        if (part2.isEmpty()) {41            for (int i = 0; i <= n; i++) {42                int p1StartLimit = i - part1.length();43                if (p1StartLimit < 0) continue;44                int startIdx = latestStart[p1StartLimit];45                if (startIdx == -1) continue;46 47                int endIdx = earliestEnd[i];48                if (endIdx == -1) continue;49 50                minLength = Math.min(minLength, (long)endIdx + part3.length() - startIdx);51            }52        } else {53            List<Integer> middles = findOccurrences(s, part2);54            for (int middleIdx : middles) {55                int p1StartLimit = middleIdx - part1.length();56                if (p1StartLimit < 0) continue;57                int startIdx = latestStart[p1StartLimit];58                if (startIdx == -1) continue;59 60                int p3StartLimit = middleIdx + part2.length();61                if (p3StartLimit > n) continue;62                int endIdx = earliestEnd[p3StartLimit];63                if (endIdx == -1) continue;64 65                minLength = Math.min(minLength, (long)endIdx + part3.length() - startIdx);66            }67        }68 69        return minLength == Long.MAX_VALUE ? -1 : (int) minLength;70    }71 72    private List<Integer> findOccurrences(String text, String pattern) {73        List<Integer> occurrences = new ArrayList<>();74        if (pattern.isEmpty()) return occurrences;75        for (int i = 0; (i = text.indexOf(pattern, i)) != -1; i++) {76            occurrences.add(i);77        }78        return occurrences;79    }80}

Complexity

Time

O(N*M), where N is `s.length()` and M is `p.length()`. The `startsWith` calls inside loops lead to this complexity. If we pre-calculate all occurrences using an efficient algorithm like KMP, the complexity becomes O(N + M).

Space

O(N), where N is the length of `s`. This is for the two auxiliary arrays `latestStart` and `earliestEnd`.

Trade-offs

Pros

Optimal time complexity of O(N + M).
Extremely fast in practice, as the main loop only involves array lookups.

Cons

More complex to implement correctly, especially handling the edge cases where parts of the pattern are empty.
Uses more memory due to the auxiliary arrays of size N.

This approach improves upon brute-force by first identifying all possible locations for the three parts of the pattern (part1, part2, part3) within the string s. After precomputing these locations, it systematically combines them using binary search to find the shortest valid match.

Algorithm

Parse the Pattern: The pattern p is first split into three components based on the two '*' characters: part1 (prefix), part2 (infix), and part3 (suffix).
Finding Occurrences: We traverse the string s to find all starting indices for part1, part2, and part3. These indices are stored in three separate lists, e.g., starts, middles, and ends. This can be done efficiently using a string searching algorithm like Knuth-Morris-Pratt (KMP) to achieve linear time for this step, though a simpler indexOf loop also works.
Combining Occurrences: The core of the algorithm is to iterate through each potential start of the match. We can iterate through each index i in the starts list. For each i, we need to find a corresponding part2 and part3 that appear after it.
1. The part2 must start at or after i + part1.length(). We can find the earliest such occurrence by performing a binary search (specifically, a lower bound search) on the middles list.
2. If a valid part2 is found at index k, the part3 must start at or after k + part2.length(). Similarly, we find the earliest such occurrence by performing a binary search on the ends list.
3. If both part2 and part3 are found (at indices k and l respectively), we have a valid matching substring s[i ... l + part3.length() - 1]. We calculate its length and update our minimum length found so far.
Final Result: After checking all possible starts from the starts list, the minimum length recorded is the answer. If no valid match is ever found, the answer is -1.

Walkthrough

The strategy is to break down the problem. A matching substring must contain part1, then part2, then part3 in that order. We can precompute all occurrences of these three parts. Then, for each occurrence of part1 starting at index i, we need to find the earliest possible valid part2 and part3 that follow. The earliest part2 must start at or after part1 ends. We can find this efficiently by doing a binary search on the sorted list of part2's start indices. Once we find a suitable part2 starting at index k, we repeat the process to find the earliest part3 that starts after part2 ends. This is also done via binary search on part3's indices. This gives us one potential matching substring. We repeat this for all occurrences of part1 and keep track of the minimum length found.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public int shortestMatchingSubstring(String s, String p) {7        String[] parts = p.split("\\*", -1);8        String part1 = parts[0];9        String part2 = parts[1];10        String part3 = parts[2];11 12        List<Integer> starts = findOccurrences(s, part1, true);13        List<Integer> middles = findOccurrences(s, part2, true);14        List<Integer> ends = findOccurrences(s, part3, false);15 16        long minLength = Long.MAX_VALUE;17 18        for (int startIdx : starts) {19            int middleSearchStart = startIdx + part1.length();20            int middlePos = Collections.binarySearch(middles, middleSearchStart);21            if (middlePos < 0) {22                middlePos = -middlePos - 1;23            }24            if (middlePos >= middles.size()) {25                continue;26            }27            int middleIdx = middles.get(middlePos);28 29            int endSearchStart = middleIdx + part2.length();30            int endPos = Collections.binarySearch(ends, endSearchStart);31            if (endPos < 0) {32                endPos = -endPos - 1;33            }34            if (endPos >= ends.size()) {35                continue;36            }37            int endIdx = ends.get(endPos);38 39            minLength = Math.min(minLength, (long)endIdx + part3.length() - startIdx);40        }41 42        return minLength == Long.MAX_VALUE ? -1 : (int) minLength;43    }44 45    private List<Integer> findOccurrences(String text, String pattern, boolean isPrefix) {46        List<Integer> occurrences = new ArrayList<>();47        if (pattern.isEmpty()) {48            // An empty pattern can match anywhere.49            // For a prefix/infix, it can start at any position.50            // For a suffix, its start position determines the end of the match.51            for (int i = 0; i <= text.length(); i++) {52                occurrences.add(i);53            }54            return occurrences;55        }56        for (int i = 0; (i = text.indexOf(pattern, i)) != -1; i++) {57            occurrences.add(i);58        }59        return occurrences;60    }61}

Complexity

Time

O(N*M + S * log K), where N is `s.length()`, M is `p.length()`, S is the number of occurrences of `part1`, and K is the number of occurrences of `part2`/`part3`. If KMP is used for finding occurrences, this becomes O(N + M + S * log K). In the worst case, this is O(N log N).

Space

O(N + M), where N is the length of `s` and M is the length of `p`. This is for storing the lists of occurrences, which in the worst case can be proportional to N.

Trade-offs

Pros

Significantly more efficient than a naive brute-force search.
Passes the given constraints for the problem.
The logic is relatively straightforward to understand and implement.

Cons

Not the most optimal solution in terms of time complexity as the log N factor can be eliminated.
The performance can vary depending on the number of occurrences of the part chosen for the outer loop. Iterating over the part with the fewest occurrences is a potential optimization.

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem