3
\$\begingroup\$

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)])
        }

    }

\$\endgroup\$
  • \$\begingroup\$ Welcome to Code Review! \$\endgroup\$ – Martin R Dec 13 '19 at 14:25
  • \$\begingroup\$ The condition s.count < t.count seems unjustified to me. IMHO s="ABCD" and t="CBCBCBBCBBB" is a valid input (the answer should be "BC"). \$\endgroup\$ – CiaPan Dec 13 '19 at 14:38
  • 1
    \$\begingroup\$ @CiaPan: The LeetCode description is a bit unclear, but according to leetcode.com/problems/minimum-window-substring/discuss/26825/…, repeated character in T must also occur repeatedly in the sliding window of S. \$\endgroup\$ – Martin R Dec 13 '19 at 14:47
  • \$\begingroup\$ @MartinR Wow, that seems an additional level of difficulty. Didn't read, thank you for specifying this requirement here. \$\endgroup\$ – CiaPan Dec 13 '19 at 16:12
6
\$\begingroup\$

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.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Thanks for the detailed answer and the code improvements you've suggested. \$\endgroup\$ – Vaibhav Singh Dec 16 '19 at 6:08
  • \$\begingroup\$ I wasn't aware of formIndex and hence was using offsetBy for iterating through the string initially. That was leading to n^2 complexity, I changed it to an array but forgot to iterate the array instead of the string. \$\endgroup\$ – Vaibhav Singh Dec 16 '19 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.