[LeetCode] 3. Longest Substring Without Repeating Characters

Problem: https://leetcode.com/problems/longest-substring-without-repeating-characters/

Use hash map to save the index of visited character.
For every character, locate the last position of this character in the hash map.

If found and the last character is inside of current substring, restart the substring after the duplicated character's last position.

Otherwise, increase current substring length.

Time Complexity = O( N ), N = len(s)
Space Complexity = O( N ), for the space used by the hash map.

from collections import defaultdict

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = defaultdict(lambda: -1)

        left = -1
        result = 0

        for right, letter in enumerate(s):
            left = max(seen[letter], left)  # shrink window if needed

            result = max(result, right - left)
            seen[letter] = right # remember the last position the letter was seen
            
        return result

A classical sliding window implementation. Count encoutered letter with hash table.

Time complexity = O ( 2 * N ), N = len(s)

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> counter = new HashMap<>();
        int left = 0;
        int result = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char rc = s.charAt(right);
            counter.put(rc, counter.getOrDefault(rc, 0) + 1);
            
            while (counter.get(rc) > 1) {
                char lc = s.charAt(left);
                counter.put(lc, counter.get(lc) - 1);
                left += 1;
            }
            
            result = Math.max(result, right - left + 1);
        }
        
        return result;
    }
}

Edited on 06/10/2022. Replaced with the Java version sliding window approach.

Edited on 06/16/2021. Added the Python version sliding window approach.