I’m trying to get in a habit of starting my mornings off with coffee and a Leetcode problem before work. Ease my way into the day and get the brain juices flowing. Let’s jump in!
Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
I spent some time thinking about this but couldn’t come up with anything faster than
O(N^2) although I can almost guarantee there is a way.
In any case, the thought is iterate through the permutations and use a set to track the characters seen. When we run into a character we’ve seen, capture the length (if the max), and reset on next initial character.
The following corner cases are what I missed in my initial solution:
- If iteration completes w/o running into a character it hasn’t seen.
There is probably a way to cleanup the logic so the seen & fallthrough code can be merged instead of copied.
There is probably a faster solution than
class Solution: def lengthOfLongestSubstring(self, s: str) -> int: if not s: return 0 seen = set() max_len = -1 for i in range(0, len(s)): seen.add(s[i]) for j in range(i+1 , len(s)): if s[j] in seen: max_len = max(max_len, len(seen)) seen.clear() break else: seen.add(s[j]) else: max_len = max(max_len, len(seen)) seen.clear() return max_len
Runtime: 508 ms, faster than 15.12% of Python3 online submissions for Longest Substring Without Repeating Characters. Memory Usage: 13.9 MB, less than 5.10% of Python3 online submissions for Longest Substring Without Repeating Characters.