Today I tackled an interesting Leetcode problem: Finding the longest substring without any duplicating characters. This problem introduced me to the dynamic sliding window technique a powerful tool that I can add to my arsenal. I implemented the solution in which I used a set to track distinct characters and two pointers l and r. When encountering a duplicate, I made the program shrink from the left to the right and removing them with a while loop. My solution runs in O(n) but it took 6558ms, which is inefficient. There must be a way to optimize it further. Any suggestions? class Solution(object): def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ longest = set() l = 0 max_num = 0 # "abcabcbb" for r in range(len(s)): # add the s[r] if not in arr while s[r] in longest: longest.remove(s[l]) l += 1 if s[r] not in longest: longest.add(s[r]) max_num = max(max_num, (r-l) + 1) print(longest) print(max_num) continue return max_num This problem helped me understand choosing the right data structure and technique to use, and how to expand and shrink a sliding window. Have you encountered this problem before? How would you optimize it? Continue reading...
