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.

Description Hints 2 Solution Video 29:10

3455. Shortest Matching Substring

Hard24.5% acceptance1 company

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 '*'.

Asked at 1 company

Amazon

Topics

Hints open one at a time

Hint 1

The pattern string p can be divided into three segments.

Hint 2

Use the KMP algorithm to locate all occurrences of each segment in s.

29:10

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def shortestMatchingSubstring(self, s: str, p: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3Case 4

Input

"abaacbaecebce"
"ba*c*ce"

Input

"baccbaadbc"
"cc*baa*adb"

Input

"a"
"**"

Input

"madlogic"
"*adlogi*"

Your code is saved on this device.Solution