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.