3. Longest Substring Without Repeating Characters

NeetCode: Longest Substring Without Repeating Characters · LeetCode: 3. Longest Substring Without Repeating Characters · Difficulty: Medium

Given a string s, return the length of the longest substring that contains no repeated character.

Example

Input:  s = "zxyzxyz"    Output: 3    ("xyz")
Input:  s = "xxxx"       Output: 1

Brute force: check every substring

For each start index, extend the substring one character at a time until a repeat appears. HashSet<Character> boxes each char, and Set.add returns false when the character is already present. HashSet<Character> boxes each char, and Set.add returns false when the character is already present. HashSet<Character> boxes each char, and Set.add returns false when the character is already present.

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

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int best = 0;
        for (int start = 0; start < s.length(); start++) {
            Set<Character> seen = new HashSet<>();
            for (int i = start; i < s.length(); i++) {
                if (!seen.add(s.charAt(i))) {
                    break;
                }
            }
            best = Math.max(best, seen.size());
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.lengthOfLongestSubstring("zxyzxyz"));
        System.out.println(s.lengthOfLongestSubstring("xxxx"));
        System.out.println(s.lengthOfLongestSubstring(""));
    }
}

3
1
0

Time: O(n²). Space: O(min(n, alphabet)).

Optimal: sliding window with last-seen positions

Keep a window [left, right] with no duplicates. Remember the last index of every character. When s.charAt(right) was last seen inside the window, jump left to just after that position. The window never moves backwards, so each character is handled once.

class Solution {
    public int lengthOfLongestSubstring(String s) {
        // lastSeen[c] = index + 1 of the last occurrence, 0 if never seen
        int[] lastSeen = new int[128];
        int left = 0;
        int best = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            left = Math.max(left, lastSeen[c]);
            best = Math.max(best, right + 1 - left);
            lastSeen[c] = right + 1;
        }
        return best;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.lengthOfLongestSubstring("zxyzxyz"));
        System.out.println(s.lengthOfLongestSubstring("xxxx"));
        System.out.println(s.lengthOfLongestSubstring(""));
        System.out.println(s.lengthOfLongestSubstring("abba"));
    }
}

3
1
0
2

Time: O(n). Space: O(1), since the table has 128 slots.

A char is a 16-bit value that indexes the array directly. The table has 128 slots because the problem restricts s to ASCII letters, digits, symbols, and spaces; a larger alphabet needs a bigger array or a HashMap<Character, Integer>. A char is a 16-bit value that indexes the array directly. The table has 128 slots because the problem restricts s to ASCII letters, digits, symbols, and spaces; a larger alphabet needs a bigger array or a HashMap<Character, Integer>. A char is a 16-bit value that indexes the array directly. The table has 128 slots because the problem restricts s to ASCII letters, digits, symbols, and spaces; a larger alphabet needs a bigger array or a HashMap<Character, Integer>. Storing index + 1 lets 0 mean "never seen" without an extra check. Taking Math.max(left, ...) matters for "abba": when the final a is seen, its old position is before the window, so left must not move backwards.