Best Time to Buy and Sell Stock
This is a good strategy for iterating on array problems. Let's build the foundation!
This is a very straightforward problem with real world application. Lets take it step by step.
Brute Force
A brute force solution here is obvious, let's go through each element in the array, and iterate every combination of elements to find the maximum profit.
for number in array
for every other number in array
if currentMaxProfit > max profit AND currentMaxProfit > 0
max profit = currentMaxProfit
return max profit
This is a very inefficient solution, with the time constraint being O(n²). We at least have consistent space because we only hold a variable for the max profit. There is a better way of going about this problem though.
For this problem, we should approach using the sliding window methodology.
[ Sliding Window ]
[ O(n) worst time + O(1) space ]
The sliding window is when we have 2 pointers representing a window range, and we either move the start of the window, or expand the window based on the criteria we are looking for. In this specific problem, we have 2 criteria:
- Move the first index (start of the window) when the end of the window is greater than the beginning of the window. In this scenario our profit would be negative so we need to reset our search.
- Expand our window when we have the criteria for a possible max profit.
Pseudocode:
while the end of the window is within the bounds of the array
if we can have a max profit
maxProfit = max(max profit, current profit)
else
reset beginning of window
end of window append by 1
At worst here we get, O(n) time performance. This is if we cannot have a viable maximum profit in the entire array. Space is still consistent, due to the various array pointers.
Let's go into implementation now.
// edge case for cases we cannot create a window.
guard prices.count > 0 else { return 0 }
var maxProf = 0 // start max profit at zero
var start = 0 // beginning of window pointer
var end = 1 // end of window pointer
while end < prices.count { // while the end of the window is within the bounds of the array
if prices[start] < prices[end] { // if the first number is less than second and we have a possible profit
maxProf = max(maxProf, prices[end] - prices[start])
} else {
start = end // reset window
}
end += 1 // move end of window always
}
return maxProf
Beautiful. This will be instrumental in future problems.
Longest Substring Without Repeating Characters
Time to turn the heat on a little bit! This sliding window is a little different than before.
Brute Force
As with most array problems, if we use some nested loops to find our condition, we will arrive at the answer (albeit with extreme inefficiency).
for letter in array
for every other letter in array
if we have not seen inner letter yet in this iteration
add to our iterative count
update longest if possible
else
break
return longest substring char count
This solution is built on us keeping track of our current longest substring at any given iteration in the array. If we add to our current iterative substring count, we need to update our global variable as well. The condition for us to reset our search is if we find a character we have seen before.
Time complexity is O(n³) due to our nested loops and substring checking. Depending on our preferred method of searching for past letters, if we use a hash table, this search is consistent O(1). Space complexity is O(n) because we need a data structure that expands for the letters we have previously seen. HashTable space complexity is O(n) where n is the number of unique characters (at worst).
[ Sliding Window ]
[ O(n²) worst time + O(n) space ]
You guessed it! We have another sliding window problem. This time we need to be really careful with our 2 window conditions. Our 2 conditions are: expanding our window or reset the front of our window. The question is, what causes these conditions AND how specifically do we reset & expand our window.
In our case, we know we need to expand our window when we have not seen a letter before (this includes the front of our window). To expand we can just move the end of our window by 1.
Otherwise we reset our window. BUT resetting our window only means we move the front by one. We need to ensure we do not skip any letter combinations.
keep a hashtable with seen letters
while the end of our window is in bounds
if we have not seen the end letter before
// expand
move end variable
update global variable
update hashtable
else
// reset window
move start of window 1 place
move end to start + 1
reset hashtable
return global variable
Time complexity here is O(n²) at worst. This occurs when we have all unique characters in our string. Our loop will essentially check every combination of substrings in this case. Space complexity is O(n) due to the expansion of the hashtable. N is representative of unique characters in our string.
Time to implement!
guard s.length > 0 else { return 0 } // edge case check
var longest = 1
var start = 0 // window start
var end = 1 // window end
let letters = Array(s) // swift optimization
var hashTable = [letters[start] : true] // HashTable with 1st letter
while end < s.length { // While in bounds
let startLetter = letters[start]
let endLetter = letters[end]
if hashTable[endLetter] == nil {
// expand window
end += 1
longest = max(longest, end - start) // update longest if possible
hashTable[endLetter] = true // add to hashTable
} else {
// reset window start
start += 1 // move start
end = start + 1 // reset end
hashTable = [letters[start] : true] // reset hash
}
}
return longest
Well done!
Longest Repeating Character Replacement
This is a particularly unique sliding window problem. I personally struggled with this one. Let's dive in.
Brute Force
There are a couple factors at play here. First off, we can check every substring available in the input string by using nested for loops. But as we check each substring what exactly are we looking for? In a given substring, we need to see if the number of letters we need to replace is less than our input K. And we know we need to replace all characters that are not equal to the most frequent character in a given substring.
Let's say for example we have a substring "ABAA" and K=2. We know that A is the most frequent letter, so every instance of a letter that isn't A needs replaced. So we can search the substring for all non-A letters and as long as that number is less than or equal to K, its a valid substring. It would look something like this
for every letter in S
for every remaining letter in S
find count of most frequent character
count of everything else = substring length - most frequent
if count of everything else <= K
continue inner loop
else
break inner loop
Pretty darn inefficient right? Let's dive into time and space complexity here. The nested loops alone give us O(n²) time. Within our loops, finding the count of the most frequent letter is another search through our substring is another O(n) time. Total this gives us O(n³). Yikes. The space complexity is at worst O(n) where n is the length of the S input string. This is because we can never have to search a substring longer than the input string.
[ Sliding Window + HashTable ]
[ O(n) time + O(n) space ]
So for efficiency sake here, we can speed a few things up. First off the searching a substring can be expedited with a HashTable. We can keep track of the counts for any given substring at all times, and have consistent time searching for each character count. We can also keep a global variable representing the most frequent character count.
For the nested loops, we can use a sliding window instead to massively decrease our algorithm time. If we have a valid substring, we can keep expanding our window to the right. If we do not have a valid substring, we need to shrink our window from the left (Move the start pointer forward). Here is the pseudocode:
for letter in string
add to hashTable
update global max character frequency value
while our substring is invalid
shrink window from the start
update HashTable accordingly
update global variable for our result
return global
With this solution, we have at worst O(n) time where n is the length of the input string. This is because the worst that can happen, is we expand our window all the way to the right, have the last letter make the substring invalid, and then shrink our window to the end. This averages out to be O(n) time. Space complexity is O(26N) because we know we are only using capital english letters, there are only 26 of those, so our HashTable storage will never be bigger than 26 Keys. This averages out to O(n) space.
Let's implement the real solution.
var charCount = [Character: Int]() // HashTable to keep track of character counts in our substring
var maxCharCount = 0 // Max Character Count, largest in our HashTable at any given moment
var result = 0 // Our return result
var start = 0 // Start of window pointer
let sArr = Array(s) // Easy Char access in Swift
for end in 0 ..< sArr.count { // while our end pointer is in bounds
var currentWindowSize = end - start + 1 // get our current window size
let endLetter = sArr[end] // end letter
var startLetter = sArr[start] // start letter
charCount[endLetter] = charCount[endLetter, default: 0] + 1 // We have a new end letter, increment its count in the HashTable
maxCharCount = max(maxCharCount, charCount[endLetter]!) // See if the newly added letter, ups the maximum char count in the substring
while (currentWindowSize - maxCharCount) > k { // If our substring is invalid (Our # of chars we need to change is bigger than we are allowed (K) )
charCount[startLetter] = charCount[startLetter]! - 1 // Decrement the start of our window count, as we are shrinking our window
start += 1 // Shrink our window forward because string is invalid
currentWindowSize = end - start + 1 // Update window size
startLetter = sArr[start] // Update Start Letter
}
result = max(result, currentWindowSize) // update our global result for the longest substring
}
return result
Sheesh!
Minimum Window Substring
Ahhh our first Leetcode Hard. No need to fear!
Brute Force
So this is definitely a tricky one. It takes some in-depth thinking to even arrive at a brute force solution.
The idea behind the brute force solution is to keep 2 hash tables. One hash table containing character counts we need for our substring to be considered 'valid', and one hash table containing the character counts of our current sliding window substring. In our example problem where s = "ADOBECODEBANC", and t = "ABC", we know we will have a hash table representing the characters we need, and that hash table will be ['A': 1, 'B': 1, 'C': 1]. When we start our hash table for the character count in our substring will be ['A': 0, 'B': 0, 'C': 0], as we have not seen any of these letters yet.
Now we slide our window. What makes a substring valid? Well that is if: for every key in our haveHashTable, the character count is ≥ the corresponding letter count in the needHashTable. For example, in our starting substring of 'A'...our haveHashTable will be ['A': 1, 'B': 0, 'C': 0], but we know that its not a valid substring because the character counts for both 'B' and 'C' are ≤ the 'B' and 'C' counts in our needHashTable (the count for each of these is 1). We will continue to slide our window until our substring is valid. What happens when our substring is valid?
If we have a valid substring, we need to globally record the length, and update our result. Then we will pop from the start of our window, until our substring is no longer valid. The repeated work here, is every time we want to check if a substring is valid, we need to loop through every key in our haveHashTable. Gross!
It would look something like this:
for letter in S
if its a character we need, update haveHashTable
while substring is valid
update global minimum variable as applicable
pop from front of window (update haveHashTable, and move the start of the window 1 place to the right)
return minimum
We know that we have O(n) time by searching through the entire string S, and if we need to go all the way forward, and then pop the front all the way to the back, that still averages out to O(n). We have O(26n) time for seeing if our substring is valid, which on average comes out to O(n) time. This comes out to be O(n²) at worst. Space complexity here is O(2n) because we need 2 hashTables that can be at most 26 Keys long, and on average O(2n) comes out to be O(n) space.
How can we make this better?
[ Sliding Window + HashTables + Global Character Count Variables ]
[ O(n) time + O(n) space ]
The idea here is, we know we have repeated work by checking if a substring is valid. So we can tweak our logic a little bit to make this linear time. Let's keep two variables: One for the number of characters we have (the sum of all keys in haveHashTable) and one for the number of characters we need (the sum of all keys in needHashTable). If numberOfCharactersWeHave == numberOfCharactersWeNeed, then we know our substring is valid. For example in the substring 'ADOBEC', our needHashTable will be ['A': 1, 'B': 1, 'C': 1], and our haveHashTable will be ['A': 1, 'B': 1, 'C': 1]. The sum of all values for both of these hashTables = 3. Since 3 == 3, we know our substring is valid.
BUT, we need to be careful here. We should only update our numberOfCharactersWeHave if we slide the window into a character we actually need, and if the character count for what we have == its count for what we need. Also, when we pop from the start of our window, we should only decrement numberOfCharactersWeHave if the letter is something we need, and the substring is no longer valid (its count for what we have is less than its count for what we need). By doing these 2 things we satisfy our condition from the brute force solution.
In the brute force solution, we only have a valid substring if the character count in haveHashTable ≥ the corresponding letter count in the needHashTable. So with our new logic, we only decrement the character count if the count falls below our needHashTable threshold. Conversely, we only increment if our character counts are equal.
In pseudocode it looks like this:
for letter in S
if its a character we need, update haveHashTable
update our numberOfCharactersWeHave only if the end letter is something we need && its count for what we have equals its count for what we need
while numberOfCharactersWeHave equals numberOfCharactersWeNeed
update global minimum variable as applicable
pop from left of window ( if the character is in our haveHashTable update it)
if the start letter is something we need, and the substring is no longer valid (its count for what we have < its count for what we need) decrement numberOfCharactersWeHave
move start pointer by 1
return minimum
The time complexity here is now liner. We still traverse the string S, but checking if a substring is valid is a consistent operation. We are only checking 2 variables. This means we now have O(n) time. The space complexity still remains O(n) due to the 2 hash tables to store character counts. Let's implement the real thing (and apologies for the extra code and comments, I wanted to make it as clear as possible).
let inputS = Array(s) // for easier swift access
let inputT = Array(t) // for easier swift access
var haveHash = [Character:Int]()
var needHash = [Character:Int]()
var slidingWindowStart = 0
var globalMinSubstringLength = Int.max
var globalMinSubstring = ""
var numberOfCharactersWeHave = 0
// set up our hashTable for letters we need
for letter in inputS { haveHash[letter] = 0 }
// set up our hashTable for letters we need
for letter in inputT { needHash[letter] = needHash[letter, default: 0] + 1 }
var numberOfCharactersWeNeed = needHash.count
for (endLetterIndex, endLetter) in inputS.enumerated() {
// update haveHash if applicable
if let endLetterCountInHaveHash = haveHash[endLetter] { haveHash[endLetter] = endLetterCountInHaveHash + 1 }
// see if our have character count can be appended.
// that is, the end letter is something we need && its count for what we have == its count for what we need
if needHash[endLetter] != nil, let needHashCount = needHash[endLetter], let haveHashCount = haveHash[endLetter], needHashCount == haveHashCount {
numberOfCharactersWeHave += 1
}
// while we have all the characters we need (the substring is valid)
while numberOfCharactersWeHave == numberOfCharactersWeNeed {
// get length of current substring
let lengthOfCurrentSubstring = (endLetterIndex - slidingWindowStart) + 1
// update global minimum substring if possible
if lengthOfCurrentSubstring < globalMinSubstringLength {
globalMinSubstring = String(inputS[slidingWindowStart...endLetterIndex])
globalMinSubstringLength = lengthOfCurrentSubstring
}
let startLetter = inputS[slidingWindowStart]
// pop from left of window if the character is in our have hash
if let haveHashStartLetterCount = haveHash[startLetter] { haveHash[startLetter] = haveHashStartLetterCount - 1 }
// if the start letter is something we need, and the substring is no longer valid (its count for what we have < its count for what we need) update our numberOfCharactersWeHave
if let needHashStartLetterCount = needHash[startLetter], let haveHashStartLetterCount = haveHash[startLetter], haveHashStartLetterCount < needHashStartLetterCount { numberOfCharactersWeHave -= 1 }
// move left window pointer
slidingWindowStart += 1
}
}
return globalMinSubstring
Conclusion
Sliding window problems can come in all shapes and sizes. Keep an eye out when you see the word 'Substring' in a problem, as it may well mean its a sliding window problem! Once you get the pattern of them down, they are easy-peasy.
