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 = &quot;ADOBECODEBANC&quot;, T = &quot;ABC&quot;
Output: &quot;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) -&gt; String {
        var end = 0
        var start = 0
        
        if s == &quot;&quot; || t == &quot;&quot; || s.count &lt; t.count {
            return &quot;&quot;
        }
        
        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 &lt; 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 &gt; end - start {
                    resLen = end - start
                   resStart = start
                }

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

    }
Performance

The main culprit for exceeding the time limit is here:

while end &lt; 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 &lt; 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: &amp;end)
    len += 1

    // ...
}


Some simplifications

Testing for an empty string can be done with isEmpty:

if s.isEmpty || t.isEmpty || s.count &lt; 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 &gt; 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..&lt;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) -&gt; 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?) -&gt; Bool {
            if let other = other {
                return length &lt; other.length
            } else {
                return true
            }
        }
    }

    if s.isEmpty || t.isEmpty || s.count &lt; 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: &amp;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 &gt; 0 {
                    distinct += 1
                }
            }
            s.formIndex(after: &amp;currentWindow.startIndex)
            currentWindow.length -= 1
        }
    }

    if let best = bestWindow {
        return String(s[best.startIndex..&lt;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.