LeetCode. 3. Longest Substring Without Repeating Characters

[Link] https://leetcode.com/problems/longest-substring-without-repeating-characters/

Sliding window

Maintain a window s[left..right] and a set containing its characters. The invariant is that the active window contains no repeated UTF-16 char. When the character at right is already in the set, remove characters from the left (advancing left) until that duplicate is gone. Then add the new character, and update the longest valid window length.

The window is always unique after each iteration. Any longest substring ending at the current position must start at or after left, because earlier starts would include a repeated character. Recording the current window length therefore considers the best valid substring ending there.

Java implementation

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> window = new HashSet<>();
        int left = 0;
        int best = 0;

        for (int right = 0; right < s.length(); right++) {
            char current = s.charAt(right);
            while (window.contains(current)) {
                window.remove(s.charAt(left));
                left++;
            }
            window.add(current);
            best = Math.max(best, right - left + 1);
        }

        return best;
    }
}

Each character enters and leaves the window at most once, so the time complexity is O(N). The set stores at most the distinct characters in the input, giving O(min(N, alphabet)) auxiliary space under LeetCode’s character set.