Longest Substring without Repeating Characters - Two Pointers / Sliding Window

Problems
27

Key here is to use a dictionary to store the indexes. Use the characters as keys. For every pass, check the dictionary to see if the character is unique. If it is, increase the window. If it is not, then check if that was the longest substring, then set the left pointer to the index of the duplicate character and the right pointer to the next character and reset the dictionary.

def longest_substring_without_repeating_characters(s: str) → int:
longest_substr = left = right = 0
unique_chars = {}

while right < len(s):
    if s[right] in unique_chars:
        # sequence broken, char is no longer unique. Check if that sequence was the longest seen so far
        longest_substr = max(longest_substr, len(unique_chars))

        # move window forward. Left should move to the value after the duplicate character
        left = unique_chars[s[right]] + 1
        right = left

        # cleanup. Reset unique character set
        unique_chars.clear()
    else:
        # character is unique. Add to set
        unique_chars[s[right]] = right

        # Check if the sequence is the longest seen so far
        longest_substr = max(longest_substr, len(unique_chars))

        # keep finding more unique characters by expanding window
        right += 1

return longest_substr
28

This one Sliding Window patterns is also worth attention

29

Solution without hashmap(actually it works as a hashmap)

public static int longestSubstringWithoutRepeatingCharacters(String s) {
    int slow = 0, fast = 0, length = s.length(), longest = Integer.MIN_VALUE;
    byte[] storage = new byte[26];

    while (fast < length) {
        storage[s.charAt(fast) - 'a']++;

        if (storage[s.charAt(fast) - 'a'] > 1) {
            longest = Math.max(longest, fast - slow);
            while (storage[s.charAt(fast) - 'a'] > 1) {
                storage[s.charAt(fast) - 'a']--;
                slow++;
            }
        }

        fast++;
    }

    return longest;
}
30

A solution using SET instead of DICTIONARY.

def longest_substring_without_repeating_characters(s: str) -> int:
    left, window, max_length = 0, set(), 0
    for right in range(len(s)):
        while s[right] in window:
            window.remove(s[left])
            left += 1
        window.add(s[right])
        max_length = max(len(window), max_length)
    
    return max_length