Minimum Window Substring in Swift exceeds LeetCode runtime check

Question

This is a popular question on LeetCode:

76. Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

A substring is a contiguous sequence of characters within the string.

Example:
Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

I converted the java solution provided by LeetCode to Swift since this is the language I am practicing in. Here is my code below:

func minWindowSlidingWindow(_ s: String, _ t: String) -> String { if s == t { return s } var uniqueCharacterHashTable: [Character: Int] = [:] for character in t { if let countOfChar = uniqueCharacterHashTable[character] { uniqueCharacterHashTable[character] = countOfChar + 1 continue } uniqueCharacterHashTable[character] = 1 } let uniqueCharactersRequired = uniqueCharacterHashTable.keys.count var uniqueCharactersFormed = 0 var currentWindowCharacterHashTable: [Character: Int] = [:] var minSequenceSize = Int.max var minimumSequenceStart = 0 var minimumSequenceEnd = 0 var currentStartIndexInt = 0 var currentEndIndexInt = 0 while currentEndIndexInt < s.count { let endIndex = s.index(s.startIndex, offsetBy: currentEndIndexInt) var currentCharacter = s[endIndex] if var characterCount = currentWindowCharacterHashTable[currentCharacter] { characterCount += 1 currentWindowCharacterHashTable[currentCharacter] = characterCount } else { currentWindowCharacterHashTable[currentCharacter] = 1 } if let _ = uniqueCharacterHashTable[currentCharacter], currentWindowCharacterHashTable[currentCharacter] == uniqueCharacterHashTable[currentCharacter] { uniqueCharactersFormed += 1 } while currentStartIndexInt <= currentEndIndexInt && uniqueCharactersFormed == uniqueCharactersRequired { let startIndex = s.index(s.startIndex, offsetBy: currentStartIndexInt) currentCharacter = s[startIndex] if minSequenceSize == Int.max || currentEndIndexInt - currentStartIndexInt + 1 < minSequenceSize { minSequenceSize = currentEndIndexInt - currentStartIndexInt + 1 minimumSequenceStart = currentStartIndexInt minimumSequenceEnd = currentEndIndexInt } if let characterCountInWindow = currentWindowCharacterHashTable[currentCharacter] { currentWindowCharacterHashTable[currentCharacter] = characterCountInWindow - 1 } if let _ = uniqueCharacterHashTable[currentCharacter], let currentCharOriginalCount = uniqueCharacterHashTable[currentCharacter], let charInWindowCount = currentWindowCharacterHashTable[currentCharacter], currentCharOriginalCount > charInWindowCount { uniqueCharactersFormed -= 1 } currentStartIndexInt += 1 } currentEndIndexInt += 1 } if minSequenceSize == Int.max { return "" } let startIndex = s.index(s.startIndex, offsetBy: minimumSequenceStart) let endIndex = s.index(s.startIndex, offsetBy: minimumSequenceEnd) return String(s[startIndex ... endIndex]) } 

This works for the basic test cases and gives the desired output (as far as I know from about 10 test cases) but as the string size gets huge like 100,000 for example - it gets super slow even though I use the same data structures (I think) as suggested in the Java solution.

Can anyone point me as to where the bottleneck in this code lies and how could I optimize this further.

Answer 1

The main bottleneck is how characters of a string are accessed. A Swift String is a collection of Characters, and a Character represents a single extended grapheme cluster, which can be one or more Unicode scalars. That makes counting and index operations like

s.count s.index(s.startIndex, offsetBy: currentEndIndexInt) s.index(s.startIndex, offsetBy: currentStartIndexInt) 

slow. Instead of repeatedly converting integers to string indices it is better to work with string indices directly. For example,

var currentEndIndexInt = 0 while currentEndIndexInt < s.count { let endIndex = s.index(s.startIndex, offsetBy: currentEndIndexInt) let currentCharacter = s[endIndex] // ... currentEndIndexInt += 1 } 

can be replaced by

var currentEndIndex = s.startIndex while currentEndIndex != s.endIndex { let currentCharacter = s[currentEndIndex] // ... s.formIndex(after: &currentEndIndex) } 

or even

for currentEndIndex in s.indices { var currentCharacter = s[currentEndIndex] // ... } 

Other simplifications: Counting the number of occurrences of the characters in a string

var uniqueCharacterHashTable: [Character: Int] = [:] for character in t { if let countOfChar = uniqueCharacterHashTable[character] { uniqueCharacterHashTable[character] = countOfChar + 1 continue } uniqueCharacterHashTable[character] = 1 } 

can be done more concisely with reduce(into:_:) and dictionary subscripts with a default value:

let uniqueCharacterHashTable = t.reduce(into: [:]) { $0[$1, default: 0] += 1 } 

In the same spirit can

if var characterCount = currentWindowCharacterHashTable[currentCharacter] { characterCount += 1 currentWindowCharacterHashTable[currentCharacter] = characterCount } else { currentWindowCharacterHashTable[currentCharacter] = 1 } 

be shortened to

currentWindowCharacterHashTable[currentCharacter, default: 0] += 1 

The let _ = ... test in

if let _ = uniqueCharacterHashTable[currentCharacter], currentWindowCharacterHashTable[currentCharacter] == uniqueCharacterHashTable[currentCharacter] { ... } 

is not necessary because nil does always compare “not equal” to a non-nil value. The test for Int.max in

if minSequenceSize == Int.max || endIndexInt - currentStartIndexInt + 1 < minSequenceSize { ... } 

is not necessary. Finally the let _ = ... test in

 if let _ = uniqueCharacterHashTable[currentCharacter], let currentCharOriginalCount = uniqueCharacterHashTable[currentCharacter], let charInWindowCount = currentWindowCharacterHashTable[currentCharacter], currentCharOriginalCount > charInWindowCount { ... } 

is not needed because the next line already does the optional assignment.

Putting it all together, the code looks like this:

func minWindowSlidingWindow(_ s: String, _ t: String) -> String { if s == t { return s } let uniqueCharacterHashTable = t.reduce(into: [:]) { $0[$1, default: 0] += 1 } let uniqueCharactersRequired = uniqueCharacterHashTable.keys.count var uniqueCharactersFormed = 0 var currentWindowCharacterHashTable: [Character: Int] = [:] var minSequenceSize = Int.max var minSequenceStart = s.startIndex var minSequenceEnd = s.startIndex var currentStartIndex = s.startIndex var currentWindowLength = 1 for currentEndIndex in s.indices { var currentCharacter = s[currentEndIndex] currentWindowCharacterHashTable[currentCharacter, default: 0] += 1 if currentWindowCharacterHashTable[currentCharacter] == uniqueCharacterHashTable[currentCharacter] { uniqueCharactersFormed += 1 } while currentStartIndex <= currentEndIndex && uniqueCharactersFormed == uniqueCharactersRequired { currentCharacter = s[currentStartIndex] if currentWindowLength < minSequenceSize { minSequenceSize = currentWindowLength minSequenceStart = currentStartIndex minSequenceEnd = currentEndIndex } if let characterCountInWindow = currentWindowCharacterHashTable[currentCharacter] { currentWindowCharacterHashTable[currentCharacter] = characterCountInWindow - 1 } if let currentCharOriginalCount = uniqueCharacterHashTable[currentCharacter], let charInWindowCount = currentWindowCharacterHashTable[currentCharacter], currentCharOriginalCount > charInWindowCount { uniqueCharactersFormed -= 1 } s.formIndex(after: &currentStartIndex) currentWindowLength -= 1 } currentWindowLength += 1 } if minSequenceSize == Int.max { return "" } return String(s[minSequenceStart...minSequenceEnd]) } 

Instead of dummy default values

var minSequenceStart = s.startIndex var minSequenceEnd = s.startIndex 

one can also use optionals, which are only assigned a value once a valid window is found.

Otherwise your code is written clearly. I would perhaps use slightly shorter variables names at some places, but that is a matter of taste.