[LeetCode] 76. Minimum Window Substring (C++)

문제

https://leetcode.com/problems/minimum-window-substring/

Minimum Window Substring - LeetCode

 

 

풀이

 

난이도: Hard

 

 모든 위치에서부터 끝까지 일일이 확인하는 것은 O(N^2)의 복잡도를 가진다. 

문자열의 길이가 최대 10,000 이기 때문에 시간 복잡도로 위험해 보인다.

 

따라서 슬라이딩 윈도우 기법을 적용해보자.

LeetCode의 solution 그림

left에서 시작해 t를 모두 가지는 right 위치까지 right를 이동시키자.

그러면 2번과 같이 중복되는 A를 여러 개 가진다면, 길이를 줄일 수 있는 가능성이 있다.

 

left를 한칸식 이동시키면서 t가 모두 들어있는지 확인하자.

만약 이동시킨 left로부터 right까지 t가 모두 들어 있지 않다면,

이번엔 right를 t를 모두 가질 수 있도록 한 칸씩 이동시키는 것을 반복한다.

 

이 과정에서 가장 짧은 길이를 가지는 것이 정답이다.

 

이 알고리즘은 left가 right를 넘어서는 경우가 없기 때문에 복잡도는 O(2N)이다.

 

 

+

사실 t에 존재하지 않는 문자는 문제를 푸는데 전혀 관련이 없다.

따라서 solution에는 각각의 t의 문자가 존재하는 위치를 Map에 저장하여 해결하기도 한다.

 

 

 

코드