Solving Leetcode Problem 76. Minimum Window Substring

Today, I will try to solve the LeetCode problem number 76, which is the Minimum Window Substring problem.

leetcode

Problem :

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is included in the window. If there is no such substring, return the empty string "".

The testcases will be generated such that the answer is unique.

substring : A substring is a contiguous non-empty sequence of characters within a string.

Example 1:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

Example 2:

Input: s = "a", t = "a"
Output: "a"
Explanation: The entire string s is the minimum window.

Example 3:

Input: s = "a", t = "aa"
Output: ""
Explanation: Both 'a's from t must be included in the window.
Since the largest window of s only has one 'a', return empty string.

Constraints:

• m == s.length
• n == t.length
• 1 <= m, n <= 105
• s and t consist of uppercase and lowercase English letters.

When i first encountered this problem, i couldn’t understand how the output could be an empty string when s=aand t=aa . The lack of clear explanations and the somewhat uninformative examples made it even more challenging to grasp.

Solution :

Counter library

from collections import Counter

s_count, t_count = Counter(), Counter(t)
        
l, r = 0, 0
min_len = float('inf')
min_winodw = ""

while r < len(s):
    s_count[s[r]] += 1
    r += 1

    while l < r and s_count & t_count == t_count:
        if r - l < min_len:
            min_len = r - l
            min_winodw = s[l:r]

        s_count[s[l]] -= 1
        l += 1

return min_winodw

The variable r serves as the right endpoint for the sliding window, while l represents the starting point.

while r < len(s):
    s_count[s[r]] += 1
    r += 1

    while l < r and s_count & t_count == t_count:
  ....
  ....

The outer while loop increments r until it reaches the end of the string s. Inside this loop, the count of the current character s[r] is incremented, and r is advanced.

The inner while loop continues expanding the window size until the current window includes all the characters from the string t.

if r - l < min_len:
    min_len = r - l
    min_winodw = s[l:r]

print(min_window) # <====== printing

s_count[s[l]] -= 1
l += 1

If the current window contains all the characters from t, the algorithm proceeds to minimize its size. Here is an example:

s =
"ADOBECODEBANC"
t =
"ABC"


ADOBEC
DOBECODEBA
OBECODEBA
BECODEBA
ECODEBA
CODEBA
ODEBANC
DEBANC
EBANC
BANC

return min_winodw

Result :

Conclusion :

If you have any suggestions on how to improve the speed of this algorithm, please leave them in the comments.

I appreciate any guidance as there is still much for me to learn. Thank you!