Minimum Window Substring - LeetCode

Problem

1. input: 문자열 s, 문자열 t
2. output: s의 부분문자열 중, t의 문자를 모두 포함하고 있는 최소 길이의 부분 문자열 리턴
3. Follow up: Could you find an algorithm that runs in O(m + n) time?
   • m == s.length
   • n == t.length
   • 1 <= m, n <= 105
   • s and t consist of uppercase and lowercase English letters.

Idea

매번 부분문자열의 모든 문자를 확인하는 것은 비효율적이므로 SlidingWindow를 사용하여, 문자 포함 여부 확인을 최소화(O(n) → O(1))하고자 하였다 → Sol1

통과는 되었지만, 매우 좋지 못한 점수를 받았다. 이는 가능한 모든 부분문자열을 완전탐색하여 O(n^2)의 연산이기 때문이다. 따라서 모든 부분 문자열을 완전탐색하는 것이 아닌, t의 문자열이 모두 포함될 가능성이 있는 문자열만 탐색하도록 하여야한다.

특정 조건을 만족하는 구간 탐색 O(n^2)을 O(n)으로 바꾸는 방법엔 투포인터가 있다. 부분 문자열 탐색에 투포인터를, 문자열 확인에 SlidingWindow를 써야한다. → Sol2

Solution

1. 모든 부분문자열 탐색 + SlidingWindow

   class Solution {
       val cntMap = hashMapOf<Char, Int>()
       fun minWindow(s: String, t: String): String {
           var tLen = 0
           var len = t.length // 부분 문자열의 길이
           while (len <= s.length) { 
               for (c in t) { // 찾아야 하는 문자별 개수 초기화
                   cntMap[c] = (cntMap[c] ?: 0) + 1
               }
               var sLen = 0
               tLen = cntMap.keys.size // 찾아야 하는 전체 문자 개수
               for (start in 0 until s.length - (len- 1)) {
                   if (start == 0) { // 처음 Window 초기화
                       for (i in 0 until len) {
                           val key = s[i]
                           if (cntMap.containsKey(key)) {
                               cntMap[key] = (cntMap[key]?: 0) - 1
                               if (cntMap[key] == 0) {
                                   sLen++
                               }
                           }
                       }
                       // 첫 Window에 모든 문자가 포함된 경우
                       if(sLen == tLen) return s.substring(0, len)
                       continue
                   }
                   // Window의 첫 문자 out
                   if (cntMap.containsKey(s[start - 1])) {
                       if (cntMap[s[start - 1]] == 0) {
                           sLen--
                       }
                       cntMap[s[start - 1]] = (cntMap[s[start - 1]]?: 0) + 1
                   }
                   // Window에 새로운 문자 in
                   if (cntMap.containsKey(s[start + (len - 1)])) {
                       cntMap[s[start + (len - 1)]] = (cntMap[s[start + (len - 1)]]?: 0) - 1
                       if (cntMap[s[start + (len - 1)]] == 0) {
                           sLen++
                       }
                   }
                   if(tLen == sLen) return s.substring(start, start + len)
               }
               len++
               cntMap.clear() // 현재 len길이의 부분문자열 모두 확인하였으므로 초기화
           }
           return ""
       }
   }
   

   시간 복잡도: 모든 부분 문자열 탐색 X WindowSlidign = n^3

   

2. 투포인터 부분문자열 탐색 + SlidingWindow

   투포인터 조정

   • 모든 문자를 포함하지 않는 경우 → right + 1
   • 모든 문자를 포함하는 경우 → left +1

   class Solution {
       fun minWindow(s: String, t: String): String {
           val array = IntArray(123){0}
   				// 찾아야 하는 문자 개수 초기화
           t.toCharArray().forEach{array[it.toInt()]++}
   				var start = 0 // 부분 문자열 시작 idx
           var end = 0 // 부분 문자열 끝 idx
           var count = t.length // 찾아야 하는 전체 문자 개수
           var minLen = Int.MAX_VALUE // 최소(정답) 길이
           var minStart = 0 // 최소(정답) 길이일때 시작 idx
           while(end < s.length) {
               val ce = s[end].toInt()
               if(array[ce] > 0) count-- // 찾아야 하는 문자일 경우 cnt - 1
               array[ce]--
               end++
               while(count == 0) { // 모든 문자를 찾은 경우
                   if(minLen > end - start) { // 최소길이인 경우 정답 갱신
                       minLen = end - start
                       minStart = start
                   }
                   val cs = s[start].toInt() // 가장 첫 문자 out
                   array[cs]++
                   if(array[cs] > 0) count++ // out 문자가 찾아야 하는 문자일 경우
                   start++
               }
           }
           return if(minLen == Int.MAX_VALUE ) "" else s.substring(minStart, minStart + minLen)
       }
   }
   

   시간 복잡도: 투포인터 부분 문자열 탐색 X SlidingWindow = n^2

   

Point

1. 두가지 알고리즘을 써야하는 문제