Shortest Covering Substring for Subsequence

HARD50 pts

You are given two strings: a source string and a pattern string. Your task is to find the shortest contiguous substring within source such that the pattern is a subsequence of that substring. A subsequence is derived from another string by deleting some or no characters without changing the relative order of the remaining characters.

If there exists no contiguous substring in source that contains pattern as a subsequence, return an empty string "". If multiple substrings of the same minimum length satisfy the condition, return the one that appears earliest (has the smallest starting index) in the source string.

Key Concepts:

A substring is a contiguous sequence of characters within a string.
A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
The goal is to find the minimum-length window in source where pattern exists as a subsequence.

Understanding Through Visualization:

For source = "abcdebdde" and pattern = "bde":

The substring "bcde" (indices 1-4) contains "bde" as a subsequence: bcd****e
The substring "bdde" (indices 5-8) also contains "bde" as a subsequence: bdd****e
Both have length 4, but "bcde" starts earlier, so we return "bcde".
Note: "deb" is NOT valid because the characters must appear in the same order as in pattern.

Example

Input

source = "abcdebdde"
pattern = "bde"

Output

"bcde"

Explanation

The substring "bcde" is the shortest contiguous portion of source that contains "bde" as a subsequence. Although "bdde" also contains "bde" as a subsequence with the same length, "bcde" appears first (starting at index 1 vs index 5), so it is returned. Note that "deb" would not be valid because the characters 'd', 'e', 'b' don't maintain the order 'b', 'd', 'e' from the pattern.

Example

Input

source = "jmeqksfrsdcmsiwvaovztaqenprpvnbstl"
pattern = "u"

Output

""

Explanation

The character 'u' does not exist anywhere in the source string, so there is no possible substring that could contain "u" as a subsequence. Therefore, we return an empty string.

Example

Input

source = "abcde"
pattern = "ace"

Output

"abcde"

Explanation

The pattern "ace" requires characters 'a', 'c', and 'e' to appear in that order. In the source "abcde", these characters are at indices 0, 2, and 4 respectively. The only substring that captures all three in order is the entire string "abcde", which is therefore returned as the shortest covering substring.

Accepted0/0·0% Acceptance

Constraints

1 ≤ source.length ≤ 2 × 10⁴
1 ≤ pattern.length ≤ 100
Both source and pattern consist of lowercase English letters only.

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

s1 =

jmeqksfrsdcmsiwvaovztaqenprpvnbstl

s2 =

Shortest Covering Substring for Subsequence

Key Concepts:

Understanding Through Visualization:

Hints

Shortest Covering Substring for Subsequence

Key Concepts:

Understanding Through Visualization:

Hints