# Shortest Matching Substring
**Difficulty:** HARD
[External](https://leetcode.com/problems/shortest-matching-substring)
Canonical: https://scaleengineer.com/dsa/problems/shortest-matching-substring
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [String Matching](https://scaleengineer.com/dsa/patterns/string-matching)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** String
---
## Problem
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 `"**ba**e**c**eb**ce**"`.

**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 <= 105`
* `2 <= p.length <= 105`
* `s` contains only lowercase English letters.
* `p` contains only lowercase English letters and exactly two `'*'`.

# Approaches
## Precomputation with Binary Search
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.
**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.
**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.
### Explanation
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.

```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int shortestMatchingSubstring(String s, String p) {
        String[] parts = p.split("\\*", -1);
        String part1 = parts[0];
        String part2 = parts[1];
        String part3 = parts[2];

        List<Integer> starts = findOccurrences(s, part1, true);
        List<Integer> middles = findOccurrences(s, part2, true);
        List<Integer> ends = findOccurrences(s, part3, false);

        long minLength = Long.MAX_VALUE;

        for (int startIdx : starts) {
            int middleSearchStart = startIdx + part1.length();
            int middlePos = Collections.binarySearch(middles, middleSearchStart);
            if (middlePos < 0) {
                middlePos = -middlePos - 1;
            }
            if (middlePos >= middles.size()) {
                continue;
            }
            int middleIdx = middles.get(middlePos);

            int endSearchStart = middleIdx + part2.length();
            int endPos = Collections.binarySearch(ends, endSearchStart);
            if (endPos < 0) {
                endPos = -endPos - 1;
            }
            if (endPos >= ends.size()) {
                continue;
            }
            int endIdx = ends.get(endPos);

            minLength = Math.min(minLength, (long)endIdx + part3.length() - startIdx);
        }

        return minLength == Long.MAX_VALUE ? -1 : (int) minLength;
    }

    private List<Integer> findOccurrences(String text, String pattern, boolean isPrefix) {
        List<Integer> occurrences = new ArrayList<>();
        if (pattern.isEmpty()) {
            // An empty pattern can match anywhere.
            // For a prefix/infix, it can start at any position.
            // For a suffix, its start position determines the end of the match.
            for (int i = 0; i <= text.length(); i++) {
                occurrences.add(i);
            }
            return occurrences;
        }
        for (int i = 0; (i = text.indexOf(pattern, i)) != -1; i++) {
            occurrences.add(i);
        }
        return occurrences;
    }
}
```
### 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.

## Linear Time Solution using Precomputed Arrays
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.
**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`.
**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`.
### Explanation
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:
1.  `latestStart[i]`: Stores the starting index of the latest `part1` that starts at or before index `i`.
2.  `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.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int shortestMatchingSubstring(String s, String p) {
        String[] parts = p.split("\\*", -1);
        String part1 = parts[0], part2 = parts[1], part3 = parts[2];
        int n = s.length();

        if (part1.isEmpty() && part2.isEmpty() && part3.isEmpty()) return 0;

        int[] latestStart = new int[n];
        Arrays.fill(latestStart, -1);
        int last = -1;
        for (int i = 0; i < n; i++) {
            if (s.startsWith(part1, i)) {
                last = i;
            }
            latestStart[i] = last;
        }

        int[] earliestEnd = new int[n + 1];
        Arrays.fill(earliestEnd, -1);
        last = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (s.startsWith(part3, i)) {
                last = i;
            }
            earliestEnd[i] = last;
        }
        for (int i = n - 2; i >= 0; i--) {
            if (earliestEnd[i] == -1) {
                earliestEnd[i] = earliestEnd[i + 1];
            }
        }

        long minLength = Long.MAX_VALUE;

        if (part2.isEmpty()) {
            for (int i = 0; i <= n; i++) {
                int p1StartLimit = i - part1.length();
                if (p1StartLimit < 0) continue;
                int startIdx = latestStart[p1StartLimit];
                if (startIdx == -1) continue;

                int endIdx = earliestEnd[i];
                if (endIdx == -1) continue;

                minLength = Math.min(minLength, (long)endIdx + part3.length() - startIdx);
            }
        } else {
            List<Integer> middles = findOccurrences(s, part2);
            for (int middleIdx : middles) {
                int p1StartLimit = middleIdx - part1.length();
                if (p1StartLimit < 0) continue;
                int startIdx = latestStart[p1StartLimit];
                if (startIdx == -1) continue;

                int p3StartLimit = middleIdx + part2.length();
                if (p3StartLimit > n) continue;
                int endIdx = earliestEnd[p3StartLimit];
                if (endIdx == -1) continue;

                minLength = Math.min(minLength, (long)endIdx + part3.length() - startIdx);
            }
        }

        return minLength == Long.MAX_VALUE ? -1 : (int) minLength;
    }

    private List<Integer> findOccurrences(String text, String pattern) {
        List<Integer> occurrences = new ArrayList<>();
        if (pattern.isEmpty()) return occurrences;
        for (int i = 0; (i = text.indexOf(pattern, i)) != -1; i++) {
            occurrences.add(i);
        }
        return occurrences;
    }
}
```
### 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.