Shortest Matching Substring - Practice Coding Problems

Shortest Matching Substring - 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.

Input & Output

Example 1 — Basic Pattern Match

$ Input: s = "abcdef", p = "a*c*f"

› Output: 3

💡 Note: The shortest substring that matches pattern "a*c*f" is "acf" (positions 0, 2, 5) with length 3. The first '*' matches empty string between 'a' and 'c', and the second '*' matches empty string between 'c' and 'f'.

Example 2 — Empty String Match

$ Input: s = "hello", p = "**"

› Output: 0

💡 Note: Pattern "**" matches any string including the empty substring. Since empty substring is valid and has length 0, the answer is 0.

Example 3 — No Match Found

$ Input: s = "abc", p = "a*z*c"

› Output: -1

💡 Note: No substring of "abc" can match pattern "a*z*c" because there's no 'z' character in the string. The pattern requires 'a', then any sequence, then 'z', then any sequence, then 'c'.

Constraints

1 ≤ s.length ≤ 1000
3 ≤ p.length ≤ 1000
p contains exactly two '*' characters
s and p consist of lowercase English letters and '*'

Visualization

Tap to expand

Understanding the Visualization

Input

String s and pattern p with exactly two '*' wildcards

Process

Find all substrings that match the pattern

Output

Return length of shortest matching substring

Key Takeaway

🎯 Key Insight: Decompose the pattern into fixed parts and use efficient algorithms to find the minimum window containing all required elements.

Asked in

G Google 45 a Amazon 38 M Microsoft 32 A Apple 25

The key insight is to decompose the pattern with two wildcards into prefix, middle, and suffix parts. The optimal approach uses two pointers to find the minimum window containing all required parts. Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two Pointers - Pattern Decomposition	O(n²)	O(1)	Split pattern into parts and use two pointers to find minimum window
Binary Search on Answer Length	O(n² log n)	O(1)	Binary search on the length and check if any substring of that length matches
Brute Force - Check All Substrings	O(n³)	O(1)	Try every possible substring and check if it matches the pattern

Two Pointers - Pattern Decomposition — Algorithm Steps

Step 1: Parse pattern into prefix, middle, suffix parts
Step 2: Find all valid starting positions for prefix
Step 3: For each start, find minimum ending position that satisfies pattern

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse Pattern

Split pattern into prefix, middle, suffix parts

Find Positions

Use pointers to find valid start and end positions

Minimize Length

For each start, find minimum valid end position

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(char* s, char* p) {
    int starPositions[2];
    int starCount = 0;
    int pLen = strlen(p);
    int sLen = strlen(s);
    
    for (int i = 0; i < pLen; i++) {
        if (p[i] == '*') {
            if (starCount < 2) starPositions[starCount] = i;
            starCount++;
        }
    }
    if (starCount != 2) return -1;
    
    int star1Pos = starPositions[0];
    int star2Pos = starPositions[1];
    int prefixLen = star1Pos;
    int middleLen = star2Pos - star1Pos - 1;
    int suffixLen = pLen - star2Pos - 1;
    
    int minLength = INT_MAX;
    
    for (int i = 0; i <= sLen; i++) {
        if (i + prefixLen > sLen) continue;
        
        // Check prefix
        int prefixMatch = 1;
        for (int j = 0; j < prefixLen; j++) {
            if (s[i + j] != p[j]) {
                prefixMatch = 0;
                break;
            }
        }
        if (!prefixMatch) continue;
        
        int startAfterPrefix = i + prefixLen;
        int minSuffixStart = startAfterPrefix + middleLen;
        
        for (int suffixStart = minSuffixStart; suffixStart <= sLen; suffixStart++) {
            if (suffixStart + suffixLen > sLen) break;
            
            // Check suffix
            int suffixMatch = 1;
            for (int j = 0; j < suffixLen; j++) {
                if (s[suffixStart + j] != p[star2Pos + 1 + j]) {
                    suffixMatch = 0;
                    break;
                }
            }
            if (!suffixMatch) continue;
            
            // Check middle
            int middleMatch = 1;
            if (middleLen > 0) {
                middleMatch = 0;
                char middle[1000];
                strncpy(middle, p + star1Pos + 1, middleLen);
                middle[middleLen] = '\0';
                
                char between[1000];
                int betweenLen = suffixStart - startAfterPrefix;
                if (betweenLen >= 0) {
                    strncpy(between, s + startAfterPrefix, betweenLen);
                    between[betweenLen] = '\0';
                    
                    if (strstr(between, middle) != NULL) {
                        middleMatch = 1;
                    }
                }
            }
            
            if (middleMatch) {
                int totalLength = suffixStart + suffixLen - i;
                if (totalLength < minLength) {
                    minLength = totalLength;
                }
                break;
            }
        }
    }
    
    return minLength == INT_MAX ? -1 : minLength;
}

int main() {
    char s[1000], p[1000];
    fgets(s, sizeof(s), stdin);
    fgets(p, sizeof(p), stdin);
    
    s[strcspn(s, "\n")] = 0;
    p[strcspn(p, "\n")] = 0;
    
    printf("%d\n", solution(s, p));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

For each starting position, scan to find minimum ending position

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for pattern parts and pointers

✓ Linear Space

28.5K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two Pointers - Pattern Decomposition — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler