Find the smallest window in a string containing all characters of another string: Swift Version

To find the smallest window from the given string containing all character of subString, will follow the sliding window approach.

Sliding Window Technique to get smallest window

Example Input:

str1: “DBEACBBABDCAAFDDCABGBA”

str2: “ABBCDC”

Expected Output: “CBBABDC”

Algorithm:

Step 1 — Get the frequency of str2 (create a subStringFrequencyMap)

Step 2 — Calculate the length of str2 that will be desireCount,

Step 3 — Take a variable matchCount and assign 0 at the beginning,

Step 4 — Take two pointers as start and end, both will initialise with -1 at the beginning

Step 5 — Traverse the str1 and increment the end pointer and check till matchCount is less than desireCount, if is it, maintain frequency of str1 and create a mainStringFrequencyMap, now check again if frequency of characters in mainStringFrequencyMap is less or equal to frequency of characters in subStringFrequencyMap, then increase the matchCount accordingly.

Step6 — Collect your first slidingWindow and check if this is smaller than outputWindow, replace the outputWindow with slidingWindow. ( Get the substring with the help of start and end pointers index form the str1 )

Step7 — Do Increment in start pointer

Step8 — Get the character from the str1 at the incremented index of start.

Step 9 — Check, if the frequency of the character in the mainStringFrequencyMap is equal to 1, remove the value from the mainStringFrequencyMap otherwise decrease to 1.

Step 10 — Now check if the frequency of the character in the mainStringFrequencyMap is less than that of the character in the subStringFrequencyMap, if it is, reduce the matchCount and increase the start pointer and repeat the process.

Note: Make sue to check your outputWindow with the slidingWindow overtime to maintain the outputWindow for the smallest window.

Source Code

private func getMinimumWindowSubString(str1: String, str2: String) -> String {
var outputWindow = ""
var subStringFrequencyMap = [String: Int]()
for char in str2 {
subStringFrequencyMap["\(char)", default: 0] += 1
}
let desireCount = str2.count
var matchCount = 0
var start = -1
var end = -1
var mainStringFrequencyMap = [String: Int]()
while(true) {
var flag1 = false
var flag2 = false
while (start < str1.count-1) && (matchCount < desireCount) {
start += 1
let char = Array(str1)[start]
mainStringFrequencyMap["\(char)", default: 0] += 1
if mainStringFrequencyMap["\(char)", default: 0] <= subStringFrequencyMap["\(char)", default: 0] {
matchCount += 1
}
flag1 = true
}
while end < start && matchCount == desireCount {
let startIndex = str1.index(str1.startIndex, offsetBy: end+1)
let endIndex = str1.index(str1.startIndex, offsetBy: start)
let slidingWindow = String(str1[startIndex...endIndex])
if (outputWindow.isEmpty) || (slidingWindow.count < outputWindow.count) {
outputWindow = slidingWindow
}
end += 1
let char = Array(str1)[end]
if mainStringFrequencyMap["\(char)"]! == 1 {
mainStringFrequencyMap.removeValue(forKey: "\(char)")
} else {
mainStringFrequencyMap["\(char)"]! -= 1
}
if mainStringFrequencyMap["\(char)", default: 0] < subStringFrequencyMap["\(char)", default: 0] {
matchCount -= 1
}
flag2 = true
}
if (!flag1 && !flag2) {
break
}
}
return outputWindow
}

Conclusion :

You will learn the followings from the above program

1. Get the frequency for character in given string

2. Get the index of character in given string to find-out the actual character

3. Get the subscript from given range