Skip to main content
Talentd

Shortest Matching Substring - Solution & Explanation

HardTwo PointersStringBinary SearchString Matching3 min readAsked at: Amazon
Practice this problem

Problem Statement

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 <= 105
  • 2 <= p.length <= 105
  • s contains only lowercase English letters.
  • p contains 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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Substring + Pattern CheckO(n^2 * m)O(1)Useful for understanding the matching rules or when input sizes are very small
Pattern Decomposition + KMP + Two PointersO(n)O(n)Optimal approach for large strings; avoids repeated substring comparisons
Pattern Decomposition + Binary Search on OccurrencesO(n log n)O(n)When segment occurrences are stored in sorted arrays and you need fast next-match lookup

Video Solution

3455. Shortest Matching Substring | KMP | 3 Pointers | Binary Search • Aryan Mittal • 1,875 views views

Watch 6 more video solutions →

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.

Ready to solve this problem?

Practice Shortest Matching Substring with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Container With Most Water