Shortest Matching Substring solution and explanation
6 more videos on this problem
3455. Shortest Matching Substring | KMP | 3 Pointers | Binary SearchAryan Mittal · 29:10 · 1K views
3455. Shortest Matching Substring (Leetcode Hard)Programming Live with Larry · 34:24 · 457 views
Shortest Matching Substring (Leetcode Biweekly 150)Soumya Bhattacharjee · 11:28 · 300 views
SHORTEST MATCHING SUBSTRING | Leetcode biweekly contest 150 solutionsCodeCrusher · 0:54 · 299 views
3455. Shortest Matching Substring | Leetcode | Biweekly Contest 150Amit Choraria · 37:43 · 145 views
100517. Shortest Matching Substring | Leetcode Biweekly Contest Solution | Leetcode | @Solution_spotSolution Spot · 0:50 · 98 views
Shortest Matching Substring || LeetCode Biweekly 150 (Problem D)Shubhii · 12:20 · 56 views
The 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.
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 <= 105scontains only lowercase English letters.pcontains only lowercase English letters and exactly two'*'.
Approach overview
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.
Solution
Thinking
pcontains exactly two stars and splits into three literalsa,b,c.|s|,|p|\le 10^5forbids a naive search from every start.The shortest match is determined by occurrence positions: after one
a, take the earliest laterb, then the earliest laterc.KMP or Z-algorithm lists every occurrence of the three pieces. A two-pointer sweep over
a's starts advancesbandc. The length is the right end ofcminus the left end ofa, or-1if none exists.
Split the pattern on its two stars into literals a, b, and c. Any of them may be empty. KMP lists every starting index of each literal in s. An empty literal matches at every index 0,1,ldots,n.
For each start i of a, advance a pointer to the earliest start j of b with j\ge i+|a|, then to the earliest start k of c with k\ge j+|b|. That match has length k+|c|-i. The minimum over all starts is the answer, or -1 when no match exists.
A later b can only push c further right, so the earliest b and the earliest c are optimal for a fixed i.
The time complexity is O(n+m) and the space complexity is O(n), where n and m are the lengths of s and p.
class Solution:
def shortestMatchingSubstring(self, s: str, p: str) -> int:
def starts(pat: str):
if not pat:
return list(range(len(s) + 1))
m = len(pat)
lps = [0] * m
length = 0
i = 1
while i < m:
if pat[i] == pat[length]:
length += 1
lps[i] = length
i += 1
elif length:
length = lps[length - 1]
else:
i += 1
res = []
i = j = 0
n = len(s)
while i < n:
if s[i] == pat[j]:
i += 1
j += 1
if j == m:
res.append(i - m)
j = lps[j - 1]
elif j:
j = lps[j - 1]
else:
i += 1
return res
a, b, c = p.split('*')
A, B, C = starts(a), starts(b), starts(c)
la, lb, lc = len(a), len(b), len(c)
ans = len(s) + 1
j = k = 0
for i in A:
while j < len(B) and B[j] < i + la:
j += 1
if j == len(B):
break
while k < len(C) and C[k] < B[j] + lb:
k += 1
if k == len(C):
break
ans = min(ans, C[k] + lc - i)
return -1 if ans > len(s) else ansclass Solution {
public int shortestMatchingSubstring(String s, String p) {
int star = p.indexOf('*');
int star2 = p.indexOf('*', star + 1);
String a = p.substring(0, star);
String b = p.substring(star + 1, star2);
String c = p.substring(star2 + 1);
int[] A = starts(s, a);
int[] B = starts(s, b);
int[] C = starts(s, c);
int ans = s.length() + 1;
int j = 0, k = 0;
for (int i : A) {
while (j < B.length && B[j] < i + a.length()) {
++j;
}
if (j == B.length) {
break;
}
while (k < C.length && C[k] < B[j] + b.length()) {
++k;
}
if (k == C.length) {
break;
}
ans = Math.min(ans, C[k] + c.length() - i);
}
return ans > s.length() ? -1 : ans;
}
private int[] starts(String s, String pat) {
int n = s.length();
if (pat.isEmpty()) {
int[] res = new int[n + 1];
for (int i = 0; i <= n; ++i) {
res[i] = i;
}
return res;
}
int m = pat.length();
int[] lps = new int[m];
for (int i = 1, len = 0; i < m;) {
if (pat.charAt(i) == pat.charAt(len)) {
lps[i++] = ++len;
} else if (len > 0) {
len = lps[len - 1];
} else {
++i;
}
}
int[] tmp = new int[n];
int cnt = 0;
for (int i = 0, j = 0; i < n;) {
if (s.charAt(i) == pat.charAt(j)) {
++i;
++j;
if (j == m) {
tmp[cnt++] = i - m;
j = lps[j - 1];
}
} else if (j > 0) {
j = lps[j - 1];
} else {
++i;
}
}
int[] res = new int[cnt];
System.arraycopy(tmp, 0, res, 0, cnt);
return res;
}
}class Solution {
public:
int shortestMatchingSubstring(string s, string p) {
int star = p.find('*');
int star2 = p.find('*', star + 1);
string a = p.substr(0, star);
string b = p.substr(star + 1, star2 - star - 1);
string c = p.substr(star2 + 1);
vector<int> A = starts(s, a), B = starts(s, b), C = starts(s, c);
int ans = s.size() + 1;
int j = 0, k = 0;
for (int i : A) {
while (j < (int) B.size() && B[j] < i + (int) a.size()) {
++j;
}
if (j == (int) B.size()) {
break;
}
while (k < (int) C.size() && C[k] < B[j] + (int) b.size()) {
++k;
}
if (k == (int) C.size()) {
break;
}
ans = min(ans, C[k] + (int) c.size() - i);
}
return ans > (int) s.size() ? -1 : ans;
}
private:
vector<int> starts(const string& s, const string& pat) {
int n = s.size();
if (pat.empty()) {
vector<int> res(n + 1);
iota(res.begin(), res.end(), 0);
return res;
}
int m = pat.size();
vector<int> lps(m);
for (int i = 1, len = 0; i < m;) {
if (pat[i] == pat[len]) {
lps[i++] = ++len;
} else if (len) {
len = lps[len - 1];
} else {
++i;
}
}
vector<int> res;
for (int i = 0, j = 0; i < n;) {
if (s[i] == pat[j]) {
++i;
++j;
if (j == m) {
res.push_back(i - m);
j = lps[j - 1];
}
} else if (j) {
j = lps[j - 1];
} else {
++i;
}
}
return res;
}
};func shortestMatchingSubstring(s string, p string) int {
star := 0
for p[star] != '*' {
star++
}
star2 := star + 1
for p[star2] != '*' {
star2++
}
a, b, c := p[:star], p[star+1:star2], p[star2+1:]
A, B, C := matchStarts(s, a), matchStarts(s, b), matchStarts(s, c)
ans := len(s) + 1
j, k := 0, 0
for _, i := range A {
for j < len(B) && B[j] < i+len(a) {
j++
}
if j == len(B) {
break
}
for k < len(C) && C[k] < B[j]+len(b) {
k++
}
if k == len(C) {
break
}
ans = min(ans, C[k]+len(c)-i)
}
if ans > len(s) {
return -1
}
return ans
}
func matchStarts(s, pat string) []int {
n := len(s)
if pat == "" {
res := make([]int, n+1)
for i := 0; i <= n; i++ {
res[i] = i
}
return res
}
m := len(pat)
lps := make([]int, m)
for i, length := 1, 0; i < m; {
if pat[i] == pat[length] {
length++
lps[i] = length
i++
} else if length > 0 {
length = lps[length-1]
} else {
i++
}
}
res := make([]int, 0)
for i, j := 0, 0; i < n; {
if s[i] == pat[j] {
i++
j++
if j == m {
res = append(res, i-m)
j = lps[j-1]
}
} else if j > 0 {
j = lps[j-1]
} else {
i++
}
}
return res
}Complexity analysis
| 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 |
Frequently asked questions
Is Shortest Matching Substring easy or hard?
Shortest Matching Substring is classified as a Hard problem. It combines multiple concepts such as string matching algorithms, wildcard pattern handling, and efficient window construction using two pointers or binary search.
Shortest Matching Substring Python/Java solution
Implementations typically precompute segment matches using KMP or another substring search routine, then iterate through occurrence lists to combine segments. The logic is identical across Python, Java, C++, and Go, differing mainly in string handling and array management.
How to solve Shortest Matching Substring in O(n)?
Split the pattern into fixed segments separated by wildcards. Use a linear string matching algorithm like KMP to find all occurrences of each segment in the main string. Then iterate through occurrences of the first segment and use pointer advancement to find the next valid occurrences of later segments, computing the minimal window length in overall O(n) time.
What is the best approach for Shortest Matching Substring?
The best approach splits the pattern around wildcard characters and searches each fixed segment using a string matching algorithm such as KMP. After collecting all segment occurrences, two pointers or binary search connect valid matches to form candidate substrings. This avoids checking every substring and typically runs in O(n) or O(n log n) time.
Is Shortest Matching Substring asked at Google/Amazon/Meta?
Hard string processing problems involving substring search, wildcard matching, and minimal windows frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often test knowledge of KMP, two pointers, and efficient substring matching techniques.
What data structure is used in Shortest Matching Substring?
The solution mainly uses arrays or lists to store starting indices of each pattern segment occurrence. Two pointers or binary search operate on these sorted index lists to efficiently connect valid matches and compute the shortest valid window.
What is the time complexity of Shortest Matching Substring?
The brute force approach takes O(n^2 * m) time because every substring is checked against the pattern. The optimized solution precomputes occurrences of pattern segments using KMP and links them with two pointers or binary search, reducing the complexity to O(n) or O(n log n) depending on how matches are located.