Watch 8 video solutions for Shortest Matching Substring, a hard level problem involving Two Pointers, String, Binary Search. This walkthrough by Aryan Mittal has 1,813 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
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 <= 1052 <= p.length <= 105s contains only lowercase English letters.p contains only lowercase English letters and exactly two '*'.Problem Overview: You are given a string s and a pattern that may include wildcard characters (such as *) representing any sequence of characters. The task is to find the length of the shortest substring of s that matches the pattern exactly under these wildcard rules.
Approach 1: Brute Force Substring Check (O(n^2 * m) time, O(1) space)
Enumerate every possible substring of s using two nested loops. For each candidate substring, run a pattern matching check that handles the wildcard behavior. This typically involves scanning both the substring and the pattern with two pointers while allowing * to consume arbitrary characters. The approach is straightforward but expensive because up to O(n^2) substrings exist and each comparison may take O(m) time.
Approach 2: Pattern Decomposition + String Matching (O(n)–O(n log n) time, O(n) space)
Split the pattern around wildcard characters into fixed segments. For example, a*b*c becomes three required substrings: a, b, and c. Use a linear-time string matching algorithm such as KMP to find all occurrences of each segment in s. Store these indices in arrays. Then connect valid occurrences using two pointers or binary search: pick an occurrence of the first segment, find the earliest valid occurrence of the second that appears after it, and then the third. The window from the start of the first match to the end of the last match forms a candidate substring. Track the minimum length across all combinations.
This method avoids scanning the entire substring repeatedly. Instead, it precomputes where each required piece appears and stitches them together efficiently. Binary search over occurrence lists keeps transitions between segments fast. The technique relies heavily on string matching, careful index management with two pointers, and optional binary search to locate the next valid segment occurrence.
Recommended for interviews: The decomposition approach with KMP and pointer/binary search coordination is the expected solution. Starting with the brute force idea shows you understand the matching requirement, but the optimized method demonstrates knowledge of substring search algorithms and how to combine them to minimize repeated work.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Substring + Pattern Check | O(n^2 * m) | O(1) | Useful for understanding the matching rules or when input sizes are very small |
| Pattern Decomposition + KMP + Two Pointers | O(n) | O(n) | Optimal approach for large strings; avoids repeated substring comparisons |
| Pattern Decomposition + Binary Search on Occurrences | O(n log n) | O(n) | When segment occurrences are stored in sorted arrays and you need fast next-match lookup |