03. Longest Substring Without Repeating Characters

Problem

Given a string s, return the length of the longest substring without repeating characters.

Explanation

First pass: brute force

My first idea was to walk the string from every starting position, keep a solMaker string with the unique characters I have seen, and stop the inner loop as soon as I hit a duplicate. I tracked three things: a count of the current substring length, the pos index where the inner loop should look next, and solMaker to know if the next char is new. This works, but it does a fresh scan from each position, so it costs O(n^2) time and O(n) space.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int sol = 0, count, pos;
        String solMaker;
        boolean isDifferent;
 
        for (int i = 0; i < s.length(); i++) {
            isDifferent = true;
            pos = i + 1;
            count = 1;
            solMaker = String.valueOf(s.charAt(i));
            while (pos < s.length() && isDifferent) {
                if (solMaker.indexOf(s.charAt(pos)) == -1) {
                    solMaker = solMaker.concat(String.valueOf(s.charAt(pos)));
                    count++;
                    pos++;
                } else {
                    isDifferent = false;
                }
            }
            sol = Math.max(sol, count);
        }
 
        return sol;
    }
}

Final pass: sliding window with a set

To avoid restarting work, I switched to a sliding window backed by a HashSet. I expand the right pointer while characters stay unique; when I hit a repeat, I shrink from the left, removing chars from the set until the repeat is gone, then keep moving right. Each character is added and removed at most once, so the algorithm runs in O(n) time with O(n) space.

Time: O(n)
Space: O(n)

Solution