Minimum Window Substring

Minimum Window Substring

문제 내용

주어진 t라고 하는 문자열이 s라고 하는 문자열에 완전히 포함되는 경우 중에

가장 작은 사이즈의 부분 문자열을 구하시오

 

접근 방법

처음에 해당 문제를 접근할때는

1Point에 Index를 두개 두어서 접근 하고자 했다.

상위와 같은 방법으로 count가 모두 0일때 Index의 min과 max를 구해서 가장 작은 문자열을 뺄려고 했는데,

이 방법은 특정 문자가 중복해서 나올경우 예를 들자면 상위 그림에서 A가 2번 나오는 것을 check하고자 한다면

Index를 Array로 관리 해야한다.

개발은 가능하겠지만 개발 복잡도나 Time Complexity에 맞지 않는 것 같다.

그래서 Two Point를 사용하는 방법으로 다시 고려 하였다.

left와 right를 이동 시켜가면서 최소 문자열 사이즈를 찾는 방법이다.

$$ t = AABC $$

이고

s가

$$ s = ADABECODEBANC $$

라고 할경우 아래와 같이 정리가 된다.

t를 Hash Map으로 관리해서 A는 2번 B는 1번 C는 1번이 모두 0이 되는 순간을 찾아야 한다.

여기서 신경써야 하는 것은 

- fromCount

이다.

Unique한 Char가 몇개가 나왔는지를 check하는게 중요하다. 모든 char가 나와서 formCount가 0이 되었을 때 left가 right쪽으로 size를 줄여가면서 다시 확인이 필요하기 때문이다.

첫번째 욺직임이다. A에서 다음 A가 나오는 곳까지 모두 2번의 A가 나왔음으로 A Count는 0이 되고

formCount는 1이 된다.

같은 방법으로 A,B가 완료 되었다.

드디어 C가 완성되면서 formcount가 3이 되었다. 이제 left가 이동할 차례이다.

left가 오른쪽으로 이동하면서 formcount가 줄게 된다.

이제 더이상 left는 욺직일 수 없다. 다시 right가 이동하면 된다.

다시 formCount가 3이 되었다. 다시 left가 욺직일 수 있다.

앞선 result보다 작지 않음으로 답이 되지 않는다.

A를 떠나면서 formCount가 늘어났다.

더이상 left나 right가 욺직이지 못함으로 여기서 정지 한다.

시간 복잡도는 최악의 경우

left가 s.length만큼 움직이고

right가 s.length만큼 움직인다.

그리고 t를 hashMap화 했음으로

$$ O( S + T ) $$

가 된다.