76. Minimum Window Substring

package LeetCode_76

/**
 * 76. Minimum Window Substring
 * https://leetcode.com/problems/minimum-window-substring/description/
 *
 * Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

Example:
Input: S = "ADOBECODEBANC", T = "ABC"
Output: "BANC"

Note:
If there is no such window in S that covers all characters in T, return the empty string "".
If there is such window, you are guaranteed that there will always be only one unique minimum window in S.
 * */
class Solution {

    fun minWindow(s: String, t: String): String {
        val map = IntArray(256)
        var left = 0
        var right = 0
        var count = t.length
        var minLen = Int.MAX_VALUE
        for (c in t) {
            //can handle lower case and upper case
            map[c.toInt()]++
        }
        var result = ""
        /*
        * 了解了第一道题目以后，这道题目也很容易思考出来。解题时，按照步骤：
        * (sliding template code ?)
           1.扩展窗口，窗口中包含一个T中子元素，count–；
           2.通过count或其他限定值，得到一个可能解。
           3.只要窗口中有可能解，那么缩小窗口直到不包含可能解。
        首先，维护一个map，一个窗口。先看右边界，当窗口扩展包含全部ABC时停下，这个时候必然有count == 0。
        但是，这个时候的结果字符串可能很长，所以我们要接着缩小左边界。
        同时，当count == 0时，我们要一直缩小左边界以找到更短的字符串。
        慢慢count>0了，表明窗口中不包含全部的T了，那么又要扩展窗口。依次类推，最终找到最短字符串。
        * */
        while (right < s.length || count == 0) {
            if (count == 0) {//find out one match string
                if (minLen > right - left + 1) {
                    minLen = right - left + 1
                    result = s.substring(left, right)
                }
                //moving left pointer
                if (map[s[left++].toInt()]++ >= 0) {
                    count++
                }
            } else {
                //S = "ADOBECODEBANC", T = "ABC"
                //find out the character in S match in map
                if (map[s[right++].toInt()]-- >= 1) {
                    count--
                }
            }
        }
        //println(result)
        return result
    }
}