Return to Answer

• 24.2k
• 2
• 37
• 95

• 24.2k
• 2
• 37
• 95

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

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 currentEndIndex = s.startIndex
 var windowLength = 1
 
 while currentEndIndex != s.endIndex {
 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 windowLength < minSequenceSize {
 minSequenceSize = windowLength
 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)
 windowLength -= 1
 }
 s.formIndex(after: &currentEndIndex)
 windowLength += 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.