問題
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.
制約
1 ≤ length of text, pattern ≤ 100,000 (ASCII)
例
例 1
入力：
text = "ADOBECODEBANC"
pattern = "ABC"
期待される出力：
expected = "BANC"入力：
std::string text = "ADOBECODEBANC";
std::string pattern = "ABC";
期待される出力：
std::string expected = "BANC";入力：
string text = "ADOBECODEBANC";
string pattern = "ABC";
期待される出力：
string expected = "BANC";解説
"BANC" contains A, B and C and nothing shorter does.
例 2
入力：
text = "a"
pattern = "aa"
期待される出力：
expected = ""入力：
std::string text = "a";
std::string pattern = "aa";
期待される出力：
std::string expected = "";入力：
string text = "a";
string pattern = "aa";
期待される出力：
string expected = "";解説
Two a's are needed but the text has only one: "".
解き方のヒント
まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。
ヒント 1
窓は、異なる文字数ではなく、必要な文字数すべてを満たす必要があります。
ヒント 2
まず広げて有効にし、そこから左を縮めて不要な文字を削りつつ有効性を保ちます。
ヒント 3
同じ最小長の窓が複数あるなら、更新時はより早い方を残します。
目安の計算量
時間 O(n)、追加メモリ O(1)
参考資料
この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。