문제
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
창은 서로 다른 문자 수가 아니라 필요한 각 문자의 개수까지 모두 만족해야 합니다.
힌트 2
유효해질 때까지 늘리고, 그다음 왼쪽을 줄여 불필요한 문자를 제거하면서 유효 상태를 유지하세요.
힌트 3
같은 최소 길이의 창이 여러 개면, 갱신할 때 더 앞선 것을 유지하세요.
예상 복잡도
시간 O(n), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.