Longest Substring Without Repeating Characters

TARGET DECK: Leetcode FILE TAGS: Medium

---

Intuition

• This problem fits the Sliding Window technique perfectly, since you are adding the length of the substring, then sliding from the left until you have no duplicates remaining.

Complexity

Runtime

$O(N)$

Space

$O(N)$ due to counter.

Code

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        counter = Counter()
        left, res = 0, 0
        for right in range(len(s)):
            counter[s[right]] += 1
            
            while left <= right and counter[s[right]] > 1:
                counter[s[left]] -= 1
                left += 1
 
            res = max(res, right - left + 1)
 
        return res

Cards

START Basic Front: Longest Substring Without Repeating Characters Back: Traditional sliding window with counter keeping track of non-duplicates.

END

---

References

• Longest Substring Without Repeating Characters