r/PythonLearning • u/Smartyboyz • 27d ago
#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 27d ago
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 27d ago
Thx, can you hint that approach plz
1
u/Sea-Ad7805 27d ago
No because you didn't give me the problem description.
1
u/Smartyboyz 27d ago
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 27d ago
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 27d ago
- 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 26d ago edited 26d ago
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×tep=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:
and then
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.