# Minimum window substring - LeetCode challenge

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

}


• Welcome to Code Review! Commented Dec 13, 2019 at 14:25
• 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"). Commented Dec 13, 2019 at 14:38
• @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. Commented Dec 13, 2019 at 14:47
• @MartinR Wow, that seems an additional level of difficulty. Didn't read, thank you for specifying this requirement here. Commented Dec 13, 2019 at 16:12

### 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.

• Thanks for the detailed answer and the code improvements you've suggested. Commented Dec 16, 2019 at 6:08
• 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. Commented Dec 16, 2019 at 6:22