76.minimum-window-substring.md

76. Minimum Window Substring

Clarification Questions

• Does it contains duplicate characters?
• Is the length of t always less than or equal to the length of s?

Test Cases

Normal Cases

Input: s = "abcdabtc", t = "abc"
Output: "abc"

Edge / Corner Cases

• The length of t is greater than s.

Input: s = "abc", t = "abcd"
Output: ""

• t contains duplicate characters.

Input: s = "abbacadda", t = "aa"
Output: "aca"

• s doesn't contain t.

Input: s = "abbacadda", t = "ijk"
Output: ""

• s and t is single character.

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

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

Sliding Window

• Window: the substring of s that contains all characters in t.
• We keep expanding the window until we have all characters in t.
• Then we start to optimize our window by shrinking it to see if the window still has all characters in t (keep updating the answer)

fun minWindow(s: String, t: String): String {
    if (t.length > s.length) return ""
    val tCount = IntArray(128)
    for (c in t) {
        tCount[c - 'A']++
    }
    val sCount = IntArray(128)
    var range = intArrayOf(-1, s.length)
    var left = 0
    for (right in 0 until s.length) {
        sCount[s[right] - 'A']++
        while (contains(sCount, tCount)) {
            if (right - left < range[1] - range[0]) {
                range[0] = left
                range[1] = right
            }
            sCount[s[left] - 'A']--
            left++
        }
    }
    return if (range[0] == -1) "" else s.substring(range[0]..range[1])
}

private fun contains(sCount: IntArray, tCount: IntArray): Boolean {
    for (i in tCount.indices) {
        if (sCount[i] < tCount[i]) return false
    }
    return true
}

• Time Complexity: O(s + t).
• Space Complexity: O(1).