[leetcode] 76. Minimum Window Substring

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

---

길이가 m, n인 문자열 s, t가 입력으로 주어진다.

t의 모든 문자가 포함되는 s의 부분 문자열들 중 최소 길이를 가지는 연속 부분 문자열을 구해라.

정답이 없다면 빈 문자열 반환.

---

투포인터로 풀었다.

t문자열의 모든 문자들의 갯수를 저장하는 cnt 배열을 만들어 세팅한다.

 

right 인덱스를 증가시키며 cnt 배열의 등장갯수를 모두 충족시킨다면 해당 right 인덱스를 부분문자열 끝으로 할 때, 해당 부분문자열을 최소 길이로 만들기 위해 left인덱스를 조정한다.

 

left 인덱스는 0부터 증가시키며 현재 탐색중인 문자가 부분문자열에서 제외된다면 cnt 배열의 문자 갯수를 충족시킬 수 없을때까지 증가시킨다.  

 

예시로 나온

s = "ADOBECODEBANC"
t = "ABC"

로 정답을 구해보자.

 

t 문자열의 갯수를 충족시킬때까지 right 인덱스를 증가시키면 인덱스 5(C)까지 탐색되고, 이 때, left 인덱스는 탐색중인 문자인 A를 제거한다면 t 문자열의 A 문자 갯수를 충족시키지 못하므로 0이된다.

right가 5일 때, 만들 수 있는 최단 부분 문자열은 "ADOBEC"

다시 right 인덱스를 증가시키며 문자열 t에 포함된 문자가 탐색될때까지 증가시킨다.

문자 B를 찾아서 right 인덱스를 세팅했을 때, left인덱스에 있는 문자 A를 제거시키면 마찬가지로 조건을 충족시키지 못하므로 left는 더이상 증가시키지 않는다.

right가 9일 때, 만들 수 있는 최단 부분 문자열은 "ADOBECODEB"

right 인덱스의 문자가 'A' 일 때, left 인덱스는 5까지 증가할 수 있다.

right가 10일 때, 만들 수 있는 최단 부분 문자열은 "CODEBA"

right 인덱스가 12일 때, 만들 수 있는 최단 부분 문자열은 "BANC"

 

이때동안 만든 부분 문자열들 중 최단 문자열은 "BANC" 이므로 해당 문자열이 정답이 된다.

 

시간복잡도는 O(n+m)

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/leetcode/hard/76.%20Minimum%20Window%20Substring.cpp