Shortest Stretch Spelling It in Order
Find the shortest contiguous piece of text from which pattern can be read in order by skipping characters: the characters of pattern must all appear in the piece, in the same order, but not necessarily next to each other. Return that piece as a string.
If several pieces are equally short, return the one that starts first. If no piece works, return the empty string "". pattern is never empty.
Example 1
text "abcdebdde"
pattern "bde"
returns "bcde"
bcde (positions 1 to 4) spells b, d, e in order; bdde (positions 5 to 8) is just as short but starts later.
Example 2
text "jmeqksfrsdcmsiwvaovztaqenprpvnbstl"
pattern "u"
returns ""
There is no u in the text.
Constraints
0 <= len(text) <= 601 <= len(pattern) <= 10textandpatternhave lowercase letters only
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Two pointers problems
- Shortest Stretch With Enough of Each LetterHard
- Stones Into a RowHard
- Stretches Between Two BoundsHard
- Busy WindowsBeginner
- Change Over k DaysBeginner
- Common StartBeginner
- Fixes to Make a MirrorBeginner
- Flip a StretchBeginner