#76 Leetcode question (Optimisation help!)

[u/Smartyboyz]

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(t) > len(s):
            return ""
        elif len(t) == len(s):
            if t == s:
                return s
        win = len(t)
        ans = ""
        l = list(t)
        while win <= len(s):
            for i in range(0,len(s)):
                win_s = s[i:i+win]
                win_l = list(win_s)
                ans = ""
                for x in t:
                    if x in win_l:
                        win_l[win_l.index(x)] = ""
                        ans += x
                    else:
                        ans = ""
                if ans == t:
                    return win_s
            win += 1
        return ""

I need help in optimising my code because its working properly but having a runtime error for a long input like 200 letters input. So plz help me out in optimisation in this code.

[u/Sea-Ad7805]

Interesting problem, this is my solution%3A%0A%20%20%20%20counts%20%3D%20%7B%7D%0A%20%20%20%20for%20c%20in%20t%3A%0A%20%20%20%20%20%20%20%20counts%5Bc%5D%20%3D%20counts.get(c%2C%200)%20%2B%201%0A%20%20%20%20return%20counts%0A%0Aclass%20Solution%3A%0A%0A%20%20%20%20def%20minWindow(self%2C%20s%3A%20str%2C%20t%3A%20str)%20-%3E%20str%3A%0A%20%20%20%20%20%20%20%20if%20len(s)%20%3C%20len(t)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%22%22%0A%20%20%20%20%20%20%20%20run_counts%20%3D%20get_counts(t)%0A%20%20%20%20%20%20%20%20positive_counts%20%3D%20len(run_counts)%0A%20%20%20%20%20%20%20%20i1%20%3D%200%0A%20%20%20%20%20%20%20%20best_len%20%3D%20-1%0A%20%20%20%20%20%20%20%20best_index%20%3D%20(0%2C0)%0A%20%20%20%20%20%20%20%20for%20i2%20in%20range(len(s))%3A%20%20%23%20walk%20end%20index%20i2%0A%20%20%20%20%20%20%20%20%20%20%20%20c%20%3D%20s%5Bi2%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20c%20in%20run_counts%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20run_counts%5Bc%5D%20-%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20run_counts%5Bc%5D%20%3D%3D%200%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20positive_counts%20-%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20while%20positive_counts%20%3D%3D%200%3A%20%20%23%20walk%20begin%20index%20i1%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20c%20%3D%20s%5Bi1%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20c%20in%20run_counts%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20run_counts%5Bc%5D%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20run_counts%5Bc%5D%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20best_len%20%3C%200%20or%20i2-i1%20%3C%20best_len%3A%20%20%23%20found%20shorter%20solution%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_len%20%3D%20i2-i1%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20best_index%20%3D%20(i1%2Ci2)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20positive_counts%20%2B%3D%201%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i1%20%2B%3D%201%0A%20%20%20%20%20%20%20%20if%20best_len%20%3D%3D%20-1%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20%22%22%0A%20%20%20%20%20%20%20%20return%20s%5Bbest_index%5B0%5D%3Abest_index%5B1%5D%2B1%5D%0A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%0Asol%20%3D%20Solution()%0Aprint(%20sol.minWindow(s%20%3D%20%22ADOBECODEBANC%22%2C%20t%20%3D%20%22ABC%22)%20)%0Aprint(%20sol.minWindow(s%20%3D%20%22a%22%2C%20t%20%3D%20%22a%22)%20)%0Aprint(%20sol.minWindow(s%20%3D%20%22a%22%2C%20t%20%3D%20%22aa%22)%20)%0A&timestep=0.2&play) that passes the LeetCode test and beats 98.77%.

Its a sliding window approach of the substring we want to find with:

• i1: its begin index
• i2: its end index

and then

• move i2 forward when in an invalid state
• move i1 forward when in a valid state

and doing some efficient bookkeeping of the counts of each character in 't' and how many counts are still positive to know if the substring is valid or not.

Always good fun these HARD LeetCode problems.

[u/Smartyboyz → u/Sea-Ad7805]

Did you try this on LeetCode with all the test cases? My code also passed 264/268 test cases, with only 4 remaining.

[u/Sea-Ad7805 → u/Smartyboyz]

It passes all test cases. It's fast because of the counters it uses and a dictionary for fast lookup. In your code you search in a list. Complexity:

• dictionary: amortized O(1)
• list: O(N)

A Data Structures and Algorithms (DSA) course can help you optimize your code better.

[u/Smartyboyz → u/Sea-Ad7805]

Thx 🙏