Last active
October 14, 2020 23:24
-
-
Save oyekanmiayo/c27377bb8473cb5ae6ca710af2c77885 to your computer and use it in GitHub Desktop.
Minimum Window Substring
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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; | |
} | |
} |
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
This is a superb explanation boss. Thank you for taking your time to explain it boss, thanks 🎉