Problem
Find the shortest contiguous substring of text that contains every character of pattern, including repeats. If several are equally short, return the leftmost.
Implement min_window(text, pattern).
Input
text: The text to search. pattern: The characters that must appear.
Output
Return the shortest window, or an empty string if none exists.
Constraints
1 ≤ length of text, pattern ≤ 100,000 (ASCII)
Examples
Input:
text = "ADOBECODEBANC"
pattern = "ABC"
Expected output:
expected = "BANC"Input:
std::string text = "ADOBECODEBANC";
std::string pattern = "ABC";
Expected output:
std::string expected = "BANC";Input:
string text = "ADOBECODEBANC";
string pattern = "ABC";
Expected output:
string expected = "BANC";Explanation
"BANC" contains A, B and C and nothing shorter does.
Input:
text = "a"
pattern = "aa"
Expected output:
expected = ""Input:
std::string text = "a";
std::string pattern = "aa";
Expected output:
std::string expected = "";Input:
string text = "a";
string pattern = "aa";
Expected output:
string expected = "";Explanation
Two a's are needed but the text has only one: "".
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
The window must cover all needed character counts, not just distinct characters.
Hint 2
Expand until valid, then shrink from the left to remove unnecessary characters while staying valid.
Hint 3
If multiple windows share the same minimum length, keep the earliest one when updating your best answer.
Expected complexity
O(n) time, O(1) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.