LeetCode 76: Minimum Window Substring - Python

I'm posting a two-pointer, sliding-window problem of LeetCode (Minimum Window Substring) solved with Python. If you have time and would like to review the code, please do so, I appreciate that.

On LeetCode, we are only allowed to change the variable names and brute force algorithms are discouraged, usually fail with TLE (Time Limit Error) or MLE (Memory Limit Error).

Problem

Given a string base_string and a string target, find the minimum window in base_string which will contain all the characters in target in complexity O(n).

Example:

Input: base_string = "ADOBECODEBANC", target = "ABC" Output: "BANC" Note:

If there is no such window in base_string that covers all characters in target, return the empty string "". If there is such window, you are guaranteed that there will always be only one unique minimum window in base_string.

Solution 1

import collections

class Solution:
def minWindow(self, base_string: str, target: str) -> str:
count_map = collections.Counter(target)
left = 0
min_left, min_right = 0, 0
target_length = len(target)

for right, char in enumerate(base_string, 1):
target_length -= count_map[char] > 0
count_map[char] -= 1
if not target_length:
while left < right and count_map[base_string[left]] < 0:
count_map[base_string[left]], left = -~count_map[base_string[left]], -~left
if not min_right or right - left <= min_right - min_left:
min_left, min_right = left, right

return base_string[min_left:min_right]



Solution 2

import collections

class Solution:
def minWindow(self, base_string: str, target: str) -> str:
count_map = collections.Counter(target)
left, right = 0, 0
min_left, min_right, min_window = 0, float('inf'), ''
target_length = len(target)

while right < len(base_string):
if count_map[base_string[right]] > 0:
target_length -= 1

count_map[base_string[right]] -= 1

while target_length == 0:
sliding_window = -~right - left

if not min_window or sliding_window < len(min_window):
min_window = base_string[left:-~right]

count_map[base_string[left]] += 1

if count_map[base_string[left]] > 0:
target_length += 1
left += 1
right += 1

return min_window


Reference

• (Down-voters please comment.) – greybeard Jun 16 at 3:52

I'm not sure if online courses even go into this, but this is the exact opposite of what good code should look like. Unless there is a dire performance requirement (which is rarer than you think) the aim is always to make your code as readable (clear/stupid/simple) as possible, so that:

1. Errors have fewer places to hide
2. It is easier to reason about what the code is doing without going into how, which in turn helps you uncover errors, and makes it easier to change.

The most important factor in readability is intent. If you can't tell what the programmer is trying to accomplish, or how they are going about it, it will be very difficult to detect bugs.

This means you first need to decide on your overall strategy, so in this case: how are you going to find this window? There are many options, here are some:

• Are you going to first get all possible windows and try each of them?
• Are you going to try all windows at position 0, then move to position 1 etc...?
• Are you going to try all windows of smallest size, then next size etc...?

In your code, I am really not sure what you're going for. Both are also big functions with a lot of variables. So I didn't even try to figure out what it does (and it would be the same in a professional code review: if I don't understand at a glance what the code is even trying to do, it gets rejected).

I'll go with that last option to give you an idea of how I would write code which makes the intention clear. You'll note that by forcing the code to clearly show its intention you also end up having to break things into smaller parts, and use clear variable names, and all of these things help.

Ps: you don't need to define a class in python ;-)

def find_window(base_string, target):
"""
Try all windows in ascending size order, left to right.
"""
base_string_length = len(base_string)

def all_chars_in_window(window):
for c in target:
if c not in window:
return False
return True

def find_match_at_size(try_length):
end = try_length
start = 0
while end <= base_string_length:
window = base_string[start:end]
if all_chars_in_window(window):
return window
start += 1
end += 1

try_length = len(target)
while (try_length <= base_string_length):
window_found = find_match_at_size(try_length)
if window_found:
return window_found
try_length += 1
return ''

target = "ABC"
expected = "BANC"

print(find_window(base_string, target))


This took 7 minutes to write, because I only had to write simple code: each bit only has a couple of variables and does something very simple. If I had forced myself to do it the way you did with all those variables and calculations, I would have been at it much longer.

Hope this helps.

• -1 Whilst this seems like ok advice, though I find some choices to be questionable. Complete disregard for the limitations imposed by LeetCode is a level of unhelpfulness that I can't personally condone. – Peilonrayz Jun 15 at 2:25
• @Peilonrayz you're right, I hadn't read those fully. I thought this was a place for telling people how they can improve their code. Having looked at it more closely, I personally cannot condone LeetCode showing people code like that :-/ – andyhasit Jun 15 at 2:31
• @Emma yes, I see I missed part of the LeetCode instructions (and misunderstood the overall point of the question). I'm still struggling to understand why LeetCode would even show code like that. That's just plain wrong. – andyhasit Jun 15 at 2:37
• +1 for @andyhasit ; this is Code Review not Assignment help... and he did a good job at pointing out the problems with this code, as well as giving a good alternative example. Computer time is way cheaper than programmer time, so making code clearer is almost always less expensive than making it faster. – pjz Jun 15 at 17:33