Shortest Match for a Two-Star Pattern

Hard

You are given a string text and a pattern pattern. The pattern consists of lowercase English letters and exactly two * characters, and it starts with a letter. Each * stands for any sequence of characters, possibly empty; the letters of the pattern must match literally. Find the shortest substring (a contiguous piece) of text that matches the whole pattern and return its length. If there is no such substring, return -1.

Example 1

text="xabyyabzcab", pattern="ab*ab*c" → 8

The piece abyyabzc fits: ab, the gap yy, ab, the gap z, then c. Its length is 8, and nothing shorter works.

Example 2

text="rotor", pattern="o**o" → 3

Both stars may stay empty: oto of length 3 fits.

Example 3

text="pattern", pattern="t*e*a" → -1

There is no a in the text after t and e.

Constraints

1 ≤ len(text) ≤ 10⁵
2 ≤ len(pattern) ≤ 10⁵
text consists of lowercase English letters
pattern consists of lowercase English letters and exactly two *
The first character of pattern is a letter

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Two Pointers String Binary Search String Matching

Similar problems

Word Near an Anchor Hard Anchor Near a Companion Medium Suffixes Echoing the Start Hard Cheapest Cut to a Subsequence Hard Phrase From Word Beginnings, Long Edition Hard

Input

text="xabyyabzcab", pattern="ab*ab*c"

Expected

Run checks the first 3 tests in your browser. Submit checks all 19 tests on the server, hidden ones included.