[LeetCode] Minimum Window Substring

문제

Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:

Input: S = "ADOBECODEBANC", T = "ABC" Output: "BANC"

Note:

• If there is no such window in S that covers all characters in T, return the empty string "".
• If there is such window, you are guaranteed that there will always be only one unique minimum window in S.

Approach

String문제는 일단 sliding window로 접근해본다.

우선 map을 이용해서 T에 나오는 글자 수를 센다.

여기서 오늘 처음 알게된 점은 map에 처음 넣는 key의 value는 0으로 초기화된다는 것

이 성질을 적극 활용해 문제를 해결해 나간다.

T에 나오는 글자 수를 다 센 후에는 sliding window의 양 끝을 가리키는 포인터를 2개와

T의 길이를 기록하는 변수를 준비한다 (count).

우선 sliding window의 끝 부분 포인터를 T에 나오는 글자가 다 포함될 때 까지 늘린다

이 때 T에 포함되는 글자가 나오면 count도 같이 줄여서 글자가 다 포함됐는지 아닌지 확인한다.

그 후 글자가 다 들어가면 sliding window의 시작 부분 포인터를 T에 나오는 글자가 다 안 포함될 때 까지 줄인다.

T에 나오는 글자가 sliding window에서 빠지게 되면 count를 1늘려 글자가 덜 포함됐음을 알린다.

글자 수를 세는 과정에서 end를 늘릴때는 map[key]--, start를 늘릴때는 map[key]++ 를 하게되는데

이 과정에서 자연스럽게 T에 포함되지 않은 글자의 map[key]는 0 이상으로 올라갈 수 없어

map.find()를 하지 않고도 T에 포함된 글자인지를 알 수 있게 된다.

또한 sliding window를 줄이는 과정에서 sliding window의 최소 길이와 그 시작 지점을 기록해 답으로 출력한다.

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_MinimumWindowSubstring.cpp

chi3236/algorithm