Shortest Stretch With Enough of Each Letter
Return the shortest stretch of text (characters next to each other) that holds every letter of need at least as many times as need holds it. A letter that appears twice in need must appear at least twice in the stretch.
If several stretches are shortest, return the leftmost one. If there is none, return "".
Example 1
text "tomato"
need "oat"
returns "ato"
The last three letters hold an o, an a and a t. No shorter stretch can hold three letters.
Example 2
text "banana"
need "aan"
returns "ana"
ana has the two a's and the n. It appears twice, and the one that starts at position 1 is further left.
Example 3
text "abc"
need "abcc"
returns ""
need asks for two c's and text has only one.
Constraints
1 <= len(text) <= 3001 <= len(need) <= 300textandneedhold lowercase letters
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Two pointers problems
- Stones Into a RowHard
- Stretches Between Two BoundsHard
- Busy WindowsBeginner
- Change Over k DaysBeginner
- Common StartBeginner
- Fixes to Make a MirrorBeginner
- Flip a StretchBeginner
- Fold and AddBeginner