Minimum Window Substring - Two Pointers / Sliding Window

Problems
23

A simpler solution:

`from collections import Counter

def get_minimum_window(s: str, p: str) → str:
# WRITE YOUR BRILLIANT CODE HERE

def subset(Cw: Counter, Cp: Counter):
    return all([Cw[x] >= Cp[x] for x in Cp.elements()])

nw, min_len, min_str = 0, float('inf'), ""
Cw, Cp = Counter(), Counter(p)

for i, c in enumerate(original):
    
    Cw[c] += 1
    nw += 1
    
    while Cw[s[i - nw + 1]] > Cp[s[i - nw + 1]]:
        Cw[s[i - nw + 1]] -= 1
        nw -= 1
        
    if subset(Cw, Cp) and (nw < min_len or (nw == min_len and s[i - nw + 1:i + 1] < min_str)):
        min_len = nw
        min_str = s[i - nw + 1:i + 1]

return min_str`
24

Another example where the test cases fail on valid outputs. They should accept all valid outputs.

25

Can someone explain how this is O(n) when you’re doing string slice inside while loop? Each slide operation is O(n) so the whole algorithm should be at least O(n^2) ?

1 Like
27

Source from leetcode discussion:

var minWindow = function (s, t) {
let hist = Array(128).fill(0);
for (let c = 0; c < t.length; c++) hist[t.charCodeAt(c)]++;

let remaining = t.length;
let left = 0,
    right = 0,
    minStart = 0,
    minLen = s.length + 1;
while (right < s.length) {
    if (--hist[s.charCodeAt(right++)] >= 0) remaining--;
    while (remaining === 0) {
        if (right - left < minLen) {
            minLen = right - left;
            minStart = left;
        }
        if (++hist[s.charCodeAt(left++)] > 0) remaining++;
    }
}

return minLen < s.length + 1
    ? s.substring(minStart, minStart + minLen)
    : "";

};

28

‘’’
public static String getMinimumWindow(String original, String check) {
int originalLength = original.length();
int checkLen = check.length();

    String smallestResult = "";
    int resultLen = Integer.MAX_VALUE;
    
    Map<Character, Integer> window = new HashMap<>();
    Map<Character, Integer> checkMap = new HashMap<>();
    int left = 0;
    int right = 0;
    
    for (int i = 0; i < checkLen; i++) {
        Character currentChar = (Character)check.charAt(i);
        if(checkMap.containsKey(currentChar)) {
            checkMap.put(currentChar, checkMap.get(currentChar) + 1);
        } else {
            checkMap.put(currentChar, 1);
        }
    }
    int have = 0;
    int need = checkMap.size();
    
    while (right < originalLength) {
        Character currentChar = (Character)original.charAt(right);
        if(window.containsKey(currentChar)) {
            window.put(currentChar, window.get(currentChar) + 1);
        } else {
            window.put(currentChar, 1);
        }
        
        if (checkMap.containsKey(currentChar) && window.get(currentChar) == checkMap.get(currentChar)) {
            have++;
        }
        
        while (have == need) {
            if(right - left + 1 <= resultLen) {
                if(smallestResult.equals("")) {
                    smallestResult = original.substring(left, right + 1);
                } else if (right - left + 1 < resultLen) {
                	smallestResult = original.substring(left, right + 1);
                } else {
                    smallestResult = smallestResult.compareTo(original.substring(left, right + 1)) > 0 ? 
                        original.substring(left, right + 1) : smallestResult;
                }
                resultLen = right - left + 1;
            }
            
            Character firstChar = (Character)original.charAt(left);
            left++;
            window.put(firstChar, window.get(firstChar) - 1);
            if (checkMap.containsKey(firstChar) && window.get(firstChar) < checkMap.get(firstChar)) {
                have--;
            }
        }
        right++;
    }
    return smallestResult;
}
29

start = 0
end = 0
current_d = {}
to_match = {char:check.count(char) for char in check}
min_length = float(‘inf’)
min_substring = None

while end < len(original):
    if original[end] not in current_d:
        current_d[original[end]] = 1
    else:
        current_d[original[end]] += 1
    
    if end - start + 1 < len(check):
        end += 1
        continue
        
    else:
        while is_equal(current_d, to_match):
            if end-start+1 < min_length:
                min_length = min(min_length, end-start+1)
                min_substring = original[start:end+1]
            elif end-start+1 == min_length:
                min_substring = min(min_substring, original[start:end+1])
            current_d[original[start]] -= 1
            if current_d[original[start]] == 0:
                del current_d[original[start]]
            start += 1
        end += 1
  

return min_substring if min_substring else ""
30

https://leetcode.com/problems/minimum-window-substring

std::string get_minimum_window(std::string original, std::string check) {
std::vector freq(128);
for(auto c : check) ++freq[c];

size_t left = 0;
size_t right = 0;
size_t start = 0;
size_t matched = 0;
size_t min_len = std::numeric_limits<size_t>::max();
   
while(right != original.size())
{
    if(freq[original[right++]]-- > 0) ++matched;
      
    while(matched == check.size())
    {
        auto len = right - left;
        if(len < min_len || (len == min_len && original.substr(left, len) < original.substr(start, len))) 
        {
            min_len = len;
            start = left;
        }
            
        if(++freq[original[left++]] > 0) --matched;
    }
}
  
return min_len == std::numeric_limits<size_t>::max() ? "" : original.substr(start, min_len);

}

31

This may be a more readable two-pointers implementation:

from math import inf
from collections import Counter

def is_sub_counter(sub_counter, counter):
return all(sub_counter[k] <= counter[k] for k in sub_counter)

def get_minimum_window(original: str, check: str) → str:
len_check, len_original = len(check), len(original)
minlen = inf
minsubstr = “”

target = Counter(check)
window = Counter(original[:len_check])
    
l, r = 0, len_check-1
while r < len_original:
    if is_sub_counter(target, window):
        # 1. check for new min
        currlen = r - l + 1
        currstr = original[l:l + currlen]
        if currlen < minlen or currlen == minlen and currstr < minsubstr:
            minlen = currlen
            minsubstr = currstr
        # 2. remove current l from window
        window[original[l]]-=1
        # 3. advance l
        l+=1
    else:
        # 1. advance r
        r+=1
        # 2. add new r to window if possible
        if r < len_original: 
            window[original[r]]+=1
        
return minsubstr
32

+1, yeah and space is O(n+k) maybe? so many substrings created there for comparison and each comparison is O(min(x,y)) which could be n, so time really is O(n^2)… ?

33

@moderators could you comment please

34

I found this problem in coderbyte

35

This solution may be more elegant:

    # WRITE YOUR BRILLIANT CODE HERE
    if len(check) > len(original): return ""

    m, n = len(original), len(check)
    ans = [-m-1, 0]
    
    def is_smaller(window_a, window_b):
        len_a = window_a[1] - window_a[0] + 1
        len_b = window_b[1] - window_b[0] + 1
        
        if len_a == len_b:  
            a = original[window_a[0]:window_a[1]]
            b = original[window_b[0]:window_b[1]]
            return a < b
        else:
            return len_a < len_b
    
    d_check = Counter(check)
    required = len(d_check.keys())
    satisfied = 0
    d = defaultdict(int)
    
    left = 0
    for right in range(m):
        if original[right] in d_check:
            d[original[right]] += 1
            if d[original[right]] == d_check[original[right]]:
                satisfied += 1
                     
        while required == satisfied:
            if is_smaller([left,right+1], ans):
                ans = [left, right+1]
                
            if original[left] in d_check:
                d[original[left]] -= 1
                if d[original[left]] < d_check[original[left]]:
                    satisfied -= 1
            
            left += 1
                
    return original[ans[0]:ans[1]]
36

My Python answer
from collections import Counter
def get_minimum_window(original: str, check: str) → str:
# WRITE YOUR BRILLIANT CODE HERE

def checkifvalid(checkmap,tempstring):
    tempmap=dict(Counter(tempstring))
    for key in checkmap.keys():
        if key not in tempmap:
            return False
        if tempmap[key]<checkmap[key]:
            return False
    return True

if len(check)>len(original):
    return ""
n=len(original)

checkmap=dict(Counter(check))
slow=0
fast=0
found=0
anslen=n
ans=original
tempstring=str()
while fast<n:
    tempstring=original[slow:fast+1]
    if checkifvalid(checkmap,tempstring):
        if fast-slow+1 < anslen or ( fast-slow+1==anslen and tempstring<=ans):
            anslen=fast-slow+1
            ans=tempstring
            found=1
            
        tempstring=tempstring[1:]
        slow+=1
    else:
        fast+=1

if found==0:
    return ""
return ans

if name == ‘main’:
original = input()
check = input()
res = get_minimum_window(original, check)
print(res)

37

Adding them at the end of the line, yes. Adding comments, definitely not bad style.