Skip to content

Instantly share code, notes, and snippets.

@oyekanmiayo
Last active October 14, 2020 23:24
Show Gist options
  • Save oyekanmiayo/c27377bb8473cb5ae6ca710af2c77885 to your computer and use it in GitHub Desktop.
Save oyekanmiayo/c27377bb8473cb5ae6ca710af2c77885 to your computer and use it in GitHub Desktop.
Minimum Window Substring
class Solution {
// This approach is O(n), where n = length of string s
// The sliding window approach uses two pointers to traverse a string in linear time. Each character is visited
// at most twice
// There's a method `mapHasAllChars` whose time complexity may not be intuitive, so it's worth mentioning. At most
// each map will contain all the characters from the ascii set (0 - 255), so we know that at most we will always visit 256
// keys every time we call this method. So note this =>
// AS LONG AS WE KNOW THE WORST CASE FOR NUMBER OF LOOP ITERATIONS BEFOREHAND, THAT LOOP'S TIME COMPLEXITY IS CONSTANT
public String minWindow(String s, String t) {
//Edge Cases
if(s == null || s.isEmpty()){
return "";
}
if (t == null || t.isEmpty()){
return "";
}
if(s.equals(t)){
return s;
}
//Map to store frequency of characters in string t
Map<Character, Integer> tFreq = new HashMap<>();
for(char c : t.toCharArray()){
tFreq.putIfAbsent(c, 0);
tFreq.put(c, tFreq.get(c) + 1);
}
//Map to store frequency of characters in the sliding window
Map<Character, Integer> charFreq = new HashMap<>();
//start and end indexes for result string
int resultStartIdx = -1;
int resultEndIdx = -1;
//start and end indexes for sliding window
int startIdx = 0;
int endIdx = 0;
while(endIdx < s.length()) {
char currChar = s.charAt(endIdx);
//Check if current character in s is also a character in t
if(tFreq.containsKey(currChar)){
charFreq.putIfAbsent(currChar, 0);
charFreq.put(currChar, charFreq.get(currChar) + 1);
}
//mapHasAllChars check if the character has the same number of keys
//and if the frequency of keys in the window is up to the frequency in string t
while(startIdx <= endIdx && mapHasAllChars(tFreq, charFreq)){
//resultStartIdx == -1 means that we haven't seen any matching window before
// (endIdx - startIdx) < (resultEndIdx - resultStartIdx) here we check if the
// current valid window has a smaller length than the smallest we've seen before
if(resultStartIdx == -1 || (endIdx + 1) - startIdx < (resultEndIdx + 1 ) - resultStartIdx){
resultStartIdx = startIdx;
resultEndIdx = endIdx;
}
//Reduce the window
char charToRemove = s.charAt(startIdx);
if(charFreq.containsKey(charToRemove) && charFreq.get(charToRemove) > 1){
charFreq.put(charToRemove, charFreq.get(charToRemove) - 1);
}else {
charFreq.remove(charToRemove);
}
startIdx++;
}
//Extend the window
endIdx++;
}
return resultStartIdx == -1 ? "" : s.substring(resultStartIdx, resultEndIdx + 1);
}
private boolean mapHasAllChars(Map<Character, Integer> tFreq, Map<Character, Integer> charFreq){
if (tFreq.size() != charFreq.size()){
return false;
}
for(Character key : tFreq.keySet()){
if(charFreq.get(key) < tFreq.get(key)){
return false;
}
}
return true;
}
}
@Youngestdev
Copy link

This is a superb explanation boss. Thank you for taking your time to explain it boss, thanks 🎉

@oyekanmiayo
Copy link
Author

This is a superb explanation boss. Thank you for taking your time to explain it boss, thanks 🎉

You're welcome!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment