Skip to content

3. Longest Substring Without Repeating Characters

Problem Link

Similar to last problem, try to think of way to minimize windows from double loops.

We'll use a sliding window with two pointers \(l\) and \(r\) such that the window always contains unique characters. We expand the window by moving r from left to right and fix it whenever it becomes invalid. When processing \(s[r]\):

  • If \(s[r]\) hasn’t appeared in the current window, we include it and update the maximum window length.
  • If \(s[r]\) has appeared before, we move \(l\) to one position after its last occurrence to restore uniqueness.

To do this efficiently, we store each character’s most recent index in a hashmap. There’s no need to explicitly remove characters between the old \(l\) and the new \(l\) as advancing \(l\) implicitly invalidates them, and the hashmap entries are overwritten as we continue scanning.

Runtime Complexity

Time: \(O(n)\), each character is only processed once

Space: \(O(m)\), m unique characters used as hashmap keys

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        idxMap = dict()
        l = 0
        for r, ch in enumerate(s):
            if ch in idxMap and idxMap[ch] >= l:
                l = idxMap[ch]+1
            idxMap[ch] = r
        return len(s)-l

func lengthOfLongestSubstring(s string) int {
    idxMap := make(map[rune]int)
    var result, l int
    for r, ch := range s {
        if val, ok := idxMap[ch]; ok && val >= l {
            l = val + 1
        }
        idxMap[ch] = r
        result = max(result, r-l+1)
    }
    return result
}