Minimum window substring - LeetCode challenge

Question

Below is my code for the “Minimum Window Substring” LeetCode problem in Swift:

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

My solution fails on a very long string, but passes all the other 267 cases apart from that. I can't figure out why the Leetcode online judge says time limit exceeded, my solution seems o(n), any help is much appreciated.

func minWindow(_ s: String, _ t: String) -> String {
        var end = 0
        var start = 0
        
        if s == "" || t == "" || s.count < t.count {
            return ""
        }
        
        var freq: [Character : Int] = [:]
        
        for curChar in t {
            if let val = freq[curChar] {
                freq[curChar] = val + 1
            } else {
                freq[curChar] = 1
            }
        }
        
        let stringArray = Array(s)
        
        var resStart = 0
        var resLen = Int.max
        
        var distinct = freq.keys.count
        
        while end < s.count {
            let curChar = stringArray[end]
            
            if let val = freq[curChar] {
                freq[curChar] = val - 1
                if val - 1 == 0 {
                    distinct -= 1
                }
            }
            
            while (distinct == 0) {
                if resLen > end - start {
                    resLen = end - start
                   resStart = start
                }

                let curStart = stringArray[start]
                if let val = freq[curStart] {
                    freq[curStart] = val + 1
                    if val + 1 > 0 {
                        distinct += 1
                    }
                }
                start += 1
            }
            
            end += 1
        }
        
        if resLen == Int.max {
            return ""
        } else {
            return String(stringArray[resStart...(resStart + resLen)])
        }

    }

Answer 1

Performance

The main culprit for exceeding the time limit is here:

while end < s.count { ... }

A Swift string is a Collection but not a RandomAccessCollection, so that the complexity of var count is \$ O(n) \$, where \$ n \$ is the number of characters in the string.

s.count is called on each iteration, so that the total complexity becomes \$ O(n^2) \$.

Since you already converted the string to an array of characters, you can simply replace the condition by

while end < stringArray.count { ... }

Arrays are RandomAccessCollections and determining their count is a \$ O(1) \$ operation. That should already improve the performance considerably for large strings.

An alternative is to iterate over/keep track of string indices instead, that makes the stringArray obsolete:

var start = s.startIndex // Start of current window
var end = s.startIndex // End of current window
var len = 0 // Length of current window

while end != s.endIndex {
    let curChar = s[end]
    s.formIndex(after: &end)
    len += 1

    // ...
}

Some simplifications

Testing for an empty string can be done with isEmpty:

if s.isEmpty || t.isEmpty || s.count < t.count {
    return ""
}

When building the frequency map you can use the dictionary subscripting with default value:

var freq: [Character : Int] = [:]
for curChar in t {
    freq[curChar, default: 0] += 1
}

and that can be further shorted using reduce(into:):

var freq = t.reduce(into: [:]) { dict, char in
    dict[char, default: 0] += 1
}

Use Optional instead of magic values

Here

var resLen = Int.max

you are using a “magic value”: Int.max indicates that no matching window has been found so far. That works because the given strings are unlikely to have \$ 2^{63} - 1 \$ characters, but it forces you to use exactly the same “magic value” at

if resLen == Int.max { ... }

Also the initial value of

var resStart = 0

is meaningless, it will be overwritten as soon as the first matching window is found.

Magic values are frowned upon in Swift because there is a dedicated language feature for the purpose: the optional values.

var resLen: Int?

clearly indicates an undefined value, and later be tested with optional binding.

A (minor) drawback is that you no longer simply compare

if resLen > end - start { ... }

but I'll come back to that later.

Use structs to combine related properties

Both the current and the best window are described by two properties (

var end = 0
var start = 0

var resStart = 0
var resLen = Int.max

or – with the above suggestion – by three properties

var start = s.startIndex // Start of current window
var end = s.startIndex // End of current window
var len = 0 // Length of current window

// Similar for best window ...

With a

struct StringWindow {
    var startIndex: String.Index
    var endIndex: String.Index
    var length: Int

    // ...
}

these related properties are nicely combined, and it makes the code more self-documenting:

var currentWindow = StringWindow(...)
var bestWindow: StringWindow?

Comparing the length against the optional bestWindow can be put into a method of that type, assigning a new best window is simply done with

bestWindow = currentWindow

and the final result can be determined with optional binding:

if let best = bestWindow {
    return String(s[best.startIndex..<best.endIndex])
} else {
    return ""
}

Putting it together

Putting all the above suggestions together the code could look like this:

func minWindow(_ s: String, _ t: String) -> String {

    struct StringWindow {
        var startIndex: String.Index
        var endIndex: String.Index
        var length: Int

        init(for string: String) {
            self.startIndex = string.startIndex
            self.endIndex = string.startIndex
            self.length = 0
        }

        func shorter(than other: StringWindow?) -> Bool {
            if let other = other {
                return length < other.length
            } else {
                return true
            }
        }
    }

    if s.isEmpty || t.isEmpty || s.count < t.count {
        return ""
    }

    var freq = t.reduce(into: [:]) { dict, char in
        dict[char, default: 0] += 1
    }
    var distinct = freq.count

    var currentWindow = StringWindow(for: s)
    var bestWindow: StringWindow?

    while currentWindow.endIndex != s.endIndex {
        let curChar = s[currentWindow.endIndex]
        s.formIndex(after: &currentWindow.endIndex)
        currentWindow.length += 1

        if let val = freq[curChar] {
            freq[curChar] = val - 1
            if val - 1 == 0 {
                distinct -= 1
            }
        }

        while distinct == 0 {
            if currentWindow.shorter(than: bestWindow) {
                bestWindow = currentWindow
            }

            let curStart = s[currentWindow.startIndex]
            if let val = freq[curStart] {
                freq[curStart] = val + 1
                if val + 1 > 0 {
                    distinct += 1
                }
            }
            s.formIndex(after: &currentWindow.startIndex)
            currentWindow.length -= 1
        }
    }

    if let best = bestWindow {
        return String(s[best.startIndex..<best.endIndex])
    } else {
        return ""
    }
}

Final remarks

• Try to use more descriptive variable names (what is var distinct) or at least document their meaning.

• Don't abbreviate variable names: use e.g. length instead of len, or startIndex instead of start.

• Determining the number of key/value entries in a dictionary can be simplified to

  var distinct = freq.count
  

  instead of freq.keys.count.

• The parentheses at

  while (distinct == 0) { ... }
  

  are not needed.