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 1:
Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.
Example 2:
Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window.
Example 3:
Input: s = "a", t = "aa" Output: "" Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string.
Constraints:
m == s.lengthn == t.length1 <= m, n <= 105sandtconsist of uppercase and lowercase English letters.
The logic is explained here https://www.youtube.com/watch?v=eS6PZLjoaq8
class SolutionString {
func helperMinLengthOfRearrangedSubstring(s: String, containing substring: String) -> (Int, [Int]) {
// lets take two dictionaries to store the count of occurences of the substring
// set the values in the have dictionary to the number of occurences
// e.g. abc will have ["a":1, "b":1, c:"1"]
let haveDict = getDictWithOriginalCountOfCharactersInSubstring(t: substring)
// initialize the need dictionary with zero values
// e.g. abc will have ["a":0, "b":0, c:"0"]
var needDict = initDictWithZeroValues(t: substring)
// lets take two pointers
var leftPointer = 0
var rightPointer = 0
// convert the string to an array of characters
let stringArray = Array(s)
// set the minimum
var minimum = Int.max
var boundaries: [Int] = [Int]()
//print(stringArray)
// always make sure, the left pointer is less than right pointer
// and right pointer is always less than the max count
while leftPointer <= rightPointer && rightPointer < stringArray.count {
// print(leftPointer, rightPointer, stringArray[rightPointer])
// check if this character is present in the substring
if needDict.keys.contains(stringArray[rightPointer]) {
// this character is present, lets increment the count
// increment value in set
needDict[stringArray[rightPointer]]! += 1
//print("contains \(stringArray[rightPointer]) \(haveDict) \(needDict)")
// check if we have all the characters in the need dictionary
// if they are the same, then lets get the minimum
if areDictsTheSame(have: haveDict, need: needDict) {
// print("they are the same \(leftPointer) \(rightPointer) \(needDict)")
if (rightPointer - leftPointer) < minimum {
minimum = rightPointer - leftPointer
boundaries = [leftPointer, rightPointer]
//print("minimum is \(minimum) \(boundaries)")
}
//print("leftPointe \(leftPointer) right \(rightPointer)")
// we will try to reduce the minimum by moving the left pointer
// lets start moving the left pointer and initialize the zero dictionary
var zeroDict = initDictWithZeroValues(t: substring)
for j in leftPointer...rightPointer {
//
if zeroDict[stringArray[j]] != nil {
// now val is not nil and the Optional has been unwrapped, so use it
zeroDict[stringArray[j]]! += 1
}
}
var newZeroDict = zeroDict
while areDictsTheSame(have: haveDict, need: newZeroDict) {
//print("they are the same inside \(zeroDict) \(leftPointer) \(rightPointer)")
// we can remove one element from the stringArray
// increase left pointer
// since we remove this element from the string, lets set
// this value to zero in the needDict
// e.g. ADOBEBANC substring=ABC
// left is at A, it satisfies the constraint that it has
// all the characters in the substring
// let's move the left one place
if needDict.keys.contains(stringArray[leftPointer]) {
needDict[stringArray[leftPointer], default: 0] -= 1
}
// find the minimum
if (rightPointer - leftPointer) < minimum {
minimum = rightPointer - leftPointer
boundaries = [leftPointer, rightPointer]
//print("minimum is \(minimum) \(boundaries)")
}
// increment left pointer
leftPointer += 1
// reset the zeroDict dictionary to zero again
newZeroDict = initDictWithZeroValues(t: substring)
// print("after zero init \(zeroDict) \(zeroDict.keys)")
// lets populate the zeroDict array again with the number of
// values present in this range
// e.g. DOBEB then we will have "d":1 "o":1 "b":2 "e":2
if leftPointer <= rightPointer {
for j in leftPointer...rightPointer {
if zeroDict[stringArray[j]] != nil {
// now val is not nil and the Optional has been unwrapped, so use it
//print("second loop",val, stringArray[j])
newZeroDict[stringArray[j]]! += 1
}
}
}
}
}
}
// increment right pointer
rightPointer += 1
}
//print("return \(minimum) \(boundaries)")
if boundaries.count == 0 {
return (0, boundaries)
}
return (minimum+1, boundaries)
}
func minWindow(_ s: String, _ t: String) -> String {
// check the constraints
if Int(t.count) > Int(pow(10.0, 5.0)) {
return ""
}
if s.count < t.count {
return ""
}
if s.count == 1 && t.count == 1 {
if s == t {
return s
} else {
return ""
}
}
let (_, boundaries) = helperMinLengthOfRearrangedSubstring(s: s, containing: t)
var returnString = ""
if boundaries.count >= 2 && boundaries[0] <= boundaries[1] {
returnString = String(s[s.index(s.startIndex, offsetBy: boundaries[0]) ... s.index(s.startIndex, offsetBy: boundaries[1])])
}
return returnString
}
func areDictsTheSame(have: [Character: Int], need: [Character: Int]) -> Bool {
for i in have.keys {
if need[i]! < have[i]! {
return false
}
}
return true
}
func initDictWithZeroValues(t: String) -> [Character: Int] {
var dict = [Character:Int]()
for char in t {
dict[char] = 0
}
return dict
}
func getDictWithOriginalCountOfCharactersInSubstring(t: String) -> [Character: Int] {
var dict = [Character:Int]()
for char in t {
if dict[char] != nil {
dict[char, default: 0] += 1
} else {
dict[char] = 1
}
}
return dict
}
}
let solutionString = SolutionString()
print(solutionString.minWindow("ADOBECODEBANC", "ABC"))
//print("Solution ", solutionString.minWindow("ab", "a"))
//print("Solution ", solutionString.minWindow("ab", "A"))
//print(solutionString.minWindow("a", "taa"))
//print(solutionString.minWindow("a", "a"))
Leave a Reply