The comments are so distracting in the code… That’s just bad style.
why in Test #1 “cdba” is not a valid answer? it has the same length as “baec”
same as Test #5 and “aabbab” vs “aababb”
MY js solution
function getMinimumWindow(original, check) {
let [left, right] = [0, -1]
const seen = new Map()
let minString = ‘’
let temp
for ( const letter of check) {
if(seen.has(letter)){
seen.set(letter, seen.get(letter)+1)
} else {
seen.set(letter, 1)
}
}
while(right < original.length) {
if([...seen.values()].reduce((a,b)=>Math.max(a,b)) <= 0) {
temp = original.substring(left, right+1);
if(temp.length < minString.length || minString == ''){
minString = temp
} else if(temp.length == minString.length ) {
if(temp < minString) {
minString = temp
}
}
if(seen.has(original[left])) {
seen.set(original[left], seen.get(original[left])+1)
}
left++
} else {
right++
if(seen.has(original[right])) {
seen.set(original[right], seen.get(original[right])-1 )
}
}
}
// WRITE YOUR BRILLIANT CODE HERE
return minString;
}
It should be at the bottom right corner
It’s important to read the question in depth. Having ties is a good edge case to consider and seek clarification for in an interview. The question does state what it wants from this situation where there are ties: “If two substrings that satisfy the condition has the same length, the one that comes lexicographically first are smaller.” Since ‘baec’ is lexicographically before ‘cdba’, you should return ‘baec’.
It’s not production code, for a learning site it’s probably better to over-explain than assume everyone understands each line.
I used a variation of the previous solution and in addition for the equality edge case used a heap:
from heapq import heappop, heappush
def get_minimum_window(original: str, check: str) -> str:
def intersects(orig_count, check_count):
for key in check_count:
original = orig_count.get(key, 0)
if check_count[key] > original:
return False
return True
if len(check) > len(original): return ''
orig_count, check_count = {}, {}
start = 0
res = []
min_len = float('inf')
for i in range(len(check)):
check_count[check[i]] = 1 + check_count.get(check[i], 0)
orig_count[original[i]] = 1 + orig_count.get(original[i], 0)
if intersects(orig_count, check_count):
min_len = len(check)
heappush(res, original[start: len(check)])
for end in range(len(check), len(original)):
orig_count[original[end]] = 1 + orig_count.get(original[end], 0)
if intersects(orig_count, check_count):
while True:
orig_count[original[start]] -= 1
if orig_count[original[start]] == 0:
orig_count.pop(original[start])
start += 1
if not intersects(orig_count, check_count):
break
substr = original[start - 1: end + 1]
if len(substr) <= min_len:
min_len = len(substr)
heappush(res, substr)
return heappop(res) if len(res) > 0 else ""
My try in java. Slightly different than the one explained in the solution above.
public static String getMinimumWindow(String s, String t) {
if(s.length() < t.length())
return "";
String result = "";
Map<Character, Integer> map = new HashMap<>();
for(char c: t.toCharArray())
map.put(c, map.getOrDefault(c, 0) + 1);
int windowStart = 0;
int matched = 0;
int minWindow = s.length() + 1;
int resStart = -1;
String smallestString = "";
for(int windowEnd = 0; windowEnd < s.length(); windowEnd++) {
char rightChar = s.charAt(windowEnd);
if(map.containsKey(rightChar)) {
map.put(rightChar, map.get(rightChar) - 1);
if(map.get(rightChar) == 0)
matched++;
}
while(matched == map.size()) {
String currSmallString = "";
if(minWindow >= windowEnd - windowStart + 1) {
minWindow = windowEnd - windowStart + 1;
resStart = windowStart;
}
char leftChar = s.charAt(windowStart++);
if(map.containsKey(leftChar)) {
if(map.get(leftChar) == 0)
matched--;
map.put(leftChar, map.get(leftChar) + 1);
}
currSmallString = s.substring(resStart, resStart + minWindow);
//Getting lexicographically first string if there is a tie.
if(smallestString.equals("") || currSmallString.length() < smallestString.length())
smallestString = currSmallString;
else {
if(currSmallString.length() == smallestString.length() && smallestString.compareTo(currSmallString) > 0) {
smallestString = currSmallString;
}
}
}
}
return smallestString;
}
My solution with comments (all test cases passed)
from collections import Counter
def get_minimum_window(original: str, check: str) → str:
# define two pointers
start = 0
end = 0
check_len = len(check)
original_len = len(original)
# special case
if original_len < check_len:
return ""
# count freq of each char in check
check_set = Counter(check)
# initialize sliding window
window = []
def check_containing(d1, d2):
# helper function to check if dict1 is contained by dict2
# check keys first, and if having the same keys, check each key's value
for k, v in d1.items():
if k not in d2 or v > d2[k]:
return False
return True
# results
res = ""
while end < original_len:
# append current char to the sliding window
window.append(original[end])
# count the freq of each char in the sliding window
window_set = Counter(window)
if check_containing(check_set, window_set):
# if "sliding window" contains all chars in "check"
# move start pointer until window doesn't contain check set
while check_containing(check_set, window_set):
window.pop(0)
window_set = Counter(window)
window_len = len(window)
start = end - window_len + 1
# get the candidate that contains "check"
new_candidate = original[start-1:end+1]
# when res is empty, set the candidate as the result
if len(res) == 0:
res = new_candidate
else:
# when we already have result, do two comparisons
# 1. compare the length of the new candidate with the exisiting result
# 2. get the lexicological smaller candidate
if len(new_candidate) <= len(res):
res = min(res, new_candidate)
end += 1
return res
What about this ?
using namespace std;
std::string get_minimum_window(std::string str, std::string check) {
// WRITE YOUR BRILLIANT CODE HERE
int left = 0;
int right = 0;
set<pair<int, string>> set;
vector<int> hist(128, 0);
for(int i = 0; i < check.size(); i++) {
hist[check[i]]++;
}
int minLen = 99999;
int remaining = check.size();
int start = 0;
while(right < str.size()) {
if(--hist[str[right++]] >= 0) remaining--;
while(remaining == 0) {
if((right - left) <= minLen) {
minLen = right - left;
start = left;
string tmp = str.substr(start, minLen);
set.insert(make_pair(minLen, tmp));
}
if(++hist[str[left++]] > 0) remaining++;
}
}
return minLen < 99999 ? (*set.begin()).second : "";
}
@MOD
It is very confusing what delta_char() is really doing. Can you please elaborate?
I have no idea what the three "if"s are doing:
if char not in window_count:
window_count[char] = 0
if window_count[char] >= check_count.get(char, 0):
satisfy_count -= 1
window_count[char] += delta
if window_count[char] >= check_count.get(char, 0):
satisfy_count += 1
I understood everything except delta char function. please give more insight about that function.
I simplified delta_char function,
int delta_char(char c, int delta, int satisfy_count, std::unordered_map<char, int>& check_count, std::unordered_map<char, int>& window_count) {
if(!window_count.count(c)) {
window_count[c]=0;
}
if(check_count.count(c)) {
if(window_count[c] >= check_count[c]) {
satisfy_count -= 1;
}
}
window_count[c] += delta;
if(check_count.count(c)) {
if(window_count[c] >= check_count[c]) {
satisfy_count += 1;
}
}
return satisfy_count;
}
int delta_char(char c, int delta, int satisfy_count, std::unordered_map<char, int>& check_count, std::unordered_map<char, int>& window_count) {
if(!window_count.count(c)) {
window_count[c]=0;
}
if(check_count.count(c)) {
if(window_count[c] >= check_count[c]) {
satisfy_count -= 1;
}
}
window_count[c] += delta;
if(check_count.count(c)) {
if(window_count[c] >= check_count[c]) {
satisfy_count += 1;
}
}
return satisfy_count;
}
The solution is very difficult to read, here is an alternative:
from collections import deque
def get_minimum_window(original: str, check: str) → str:
____# O(n) time and space
____result = ‘’
____check_letters = set(check)
____counts = Counter(check)
____window = deque()
____for c in original:
________window.append(c)
________if c in check_letters:
____________counts[c] -= 1
____________while all(counts[c] <= 0 for c in counts) and window:
________________if len(result) == 0 or len(window) < len(result):
____________________result = “”.join(window)
________________elif len(window) == len(result):
____________________tmp = “”.join(window)
____________________if tmp <= result:
________________________result = tmp
________________c = window.popleft()
________________if c in check_letters:
____________________counts[c] += 1
____return result
Well formatting got me …