[LeetCode][Kotlin] 76. Minimum Window Substring

76. Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

 

The testcases will be generated such that the answer is unique.

각각 길이가 m과 n인 두 개의 문자열 s와 t가 주어지면 t의 모든 문자(중복 포함)가 윈도우에 포함되도록 s의 최소 윈도우 하위 문자열 을 반환합니다. 그러한 하위 문자열이 없으면 빈 문자열 ""을 반환합니다. 

테스트 케이스는 답이 고유하도록 생성됩니다.

 

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"

Output: "BANC"

Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

 

Example 2:

Input: s = "a", t = "a"

Output: "a"

Explanation: The entire string s is the minimum window.

 

Example 3:

Input: s = "a", t = "aa"

Output: ""

Explanation: Both 'a's from t must be included in the window.

Since the largest window of s only has one 'a', return empty string.

 

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 10^5
• s and t consist of uppercase and lowercase English letters.

---

코드

• Example 1 : ADOBEC, (DOBE, OBE, BE, E)CODEBA, (ODE, DE, E)BANC

class Solution {
    fun minWindow(s: String, t: String): String {
        if (t.isEmpty()) return ""

        val count = HashMap<Char, Int>()
        t.forEach { count[it] = count.getOrDefault(it, 0) + 1 }

        var have = 0
        val res = IntArray(2) { -1 }
        var resLen = Int.MAX_VALUE
        var l = 0
        val hm = HashMap<Char, Int>()

        for (r in s.indices) {
            hm[s[r]] = hm.getOrDefault(s[r], 0) + 1

            if (s[r] in count && hm[s[r]] == count[s[r]]!!) {
                have++
            }

            while (have == count.size) {
                if ((r - l + 1) < resLen) {
                    res[0] = l
                    res[1] = r
                    resLen = r - l + 1
                }

                hm[s[l]] = hm.getOrDefault(s[l], 0) - 1
                if (s[l] in count && hm.getOrDefault(s[l], 0) < count[s[l]]!!) {
                    have--
                }
                l++
            }
        }

        return if (res[0] == -1) "" else s.substring(res[0]..res[1])
    }
}