Minimum window substring not sliding correctly

Question

Problem

Minimum Window Substring 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.

Link for the problem

Logic

My logic is the following

Create a char-freq dict t_freq for t, where you update and fill the characters with their frequencies
Create a char-freq dict s_freq for the window in s and only the letters that are in t.
Once you reach a stage where t_freq == s_freq you compare lengths and try to find the min_len and min_ans
Then you slide windows on search for finding better options (smaller lengths)

Code

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if s == t:
            return s
        curr_len = 0
        min_len = float("inf")

        t_freq = {char: 0 for char in set(t)}
        s_freq = {char: 0 for char in set(t)}
        for char in t:
            t_freq[char] +=1
        i=0
        j=0
        N = len(s)
        min_ans = ""
        while j < N:
            if s[j] in s_freq:
                s_freq[s[j]] +=1
            if t_freq == s_freq:
                curr_len = j-i+1
                min_len = min(min_len, curr_len)
                min_ans = s[i:j+1]
                if s[i] in s_freq:
                    s_freq[s[i]] -= 1
                i+=1
            j+=1
        return min_ans

Issue

The issue is I am not sliding the windows well. It does not consider other options. For example in the test case

s = "AOBCOBAC", t = "ABC"

it returns "AOBC", which fair that it finds the first instance of the substring and it calculates length. But it never considers "BAC" in future because my guess is i does not increment enough times for the entire dict to be 0 so it can process "BAC" as {C:1, B:1, A:1} aka i am not sliding windows so it covers every part/type of substring. What do I do?

Unmitigated · Accepted Answer · 2024-03-22 14:56:12Z

Maintain the left and right index of the current window. For each possible starting (left) index of a window, move the right index forward until the frequency of each character has reached the minimum requirement. Do not compare the two dictionaries of frequencies directly as that is linear in the size of the dictionaries; instead, you can keep a count of how many characters have matched so far.

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        from collections import Counter
        t_count = Counter(t)
        curr_count = Counter()
        n = len(s)
        l = r = good = 0
        start = n
        size = n + 1
        for l in range(n):
            while r < n and good != len(t_count):
                curr_count[s[r]] += 1
                if curr_count[s[r]] == t_count[s[r]]: good += 1
                r += 1
            if good == len(t_count) and r - l < size:
                start = l
                size = r - l
            curr_count[s[l]] -= 1
            if curr_count[s[l]] < t_count[s[l]]: good -= 1
        return s[start:start + size]

Collectives™ on Stack Overflow

Minimum window substring not sliding correctly

Problem

Logic

Code

Issue

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Problem

Logic

Code

Issue

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related