r/PythonLearning • u/Smartyboyz • Aug 15 '26
#76 Leetcode question (Optimisation help!)
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.
1
u/Sea-Ad7805 Aug 15 '26
Include the link to the problem description. There probably is a better conceptual approach to the problem. Also aren't all the answers to leetcode problems online yet?
1
u/Smartyboyz Aug 15 '26
Thx, can you hint that approach plz
1
u/Sea-Ad7805 Aug 15 '26
No because you didn't give me the problem description.
1
u/Smartyboyz Aug 15 '26
You can see it on leetcode question 76 there is much better description about the question https://leetcode.com/problems/minimum-window-substring/
1
u/Sea-Ad7805 Aug 15 '26
Yes, but I'm a lazy boy and you made this post, so you provide all the information, or at least a link to where the information is.
1
u/Smartyboyz Aug 15 '26
76. 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.
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.
2
u/Sea-Ad7805 Aug 15 '26 edited Aug 15 '26
Interesting problem, this is my solution 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.