LeetCode 76: Minimum Window Substring - Python

Question

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

• Question

• Solution

• Discussion

Answer 1

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.

So the real focus should be on making it clear from your code what your intention is, preferably baked into the code itself (structure, variable names etc...) and failing that, add comments.

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 '' base_string = "ADOBECODEBANC" 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.