LeetCode Study Note | Problem 3: Longest Substring Without Repeating Characters

Problem Overview

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

Example：

Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Initial Attempt & Lessons Learned

My first attempt used a sliding window in concept, but the logic was off. I tracked each character using a HashSet<String> and manually checked s.substring(j-1, j) each step.

public int lengthOfLongestSubstring(String s) {
    int i = 0, j = 1;
    int max = 0;
    HashSet<String> strings = new HashSet<>();
    while (j < s.length() && i < j) {
        if (!strings.contains(s.substring(j - 1, j))) {
            strings.add(s.substring(j - 1, j));
            j++;
        } else {
            strings.remove(s.substring(j - 1, j));
            i++;
            max = Math.max(max, j - i);
        }
    }
    max = Math.max(max, j - i);
    return max;
}

At first glance, it seemed reasonable. But edge cases like "abcdec" exposed the flaw:

→ I was checking and removing only the most recent character, rather than resolving the true duplicate earlier in the window.

The Breakthrough: Understanding Sliding Window Properly

The core insight is this:

When a duplicate is found, we must move the left pointer i forward until the duplicate is removed from the window — not just remove the current character.

This ensures the window always contains unique characters and expands as far as possible before shrinking.

Final Correct Version (Java)

public int lengthOfLongestSubstring(String s) {
    Set<Character> set = new HashSet<>();
    int i = 0, j = 0, max = 0;
    while (j < s.length()) {
        char ch = s.charAt(j);
        if (!set.contains(ch)) {
            set.add(ch);
            j++;
            max = Math.max(max, j - i);
        } else {
            set.remove(s.charAt(i));
            i++;
        }
    }
    return max;
}

This version uses two pointers (i, j) to maintain a valid window where all characters are unique. We expand j if the character is unseen, and move i to shrink the window if a duplicate is found.

Key Takeaways

• Sliding window is not just about moving pointers — it’s about maintaining a valid state (here: uniqueness).

• Don’t just react to duplicates — resolve them completely by adjusting the window from the left.

• Use sets for O(1) lookup when uniqueness is the constraint.

• Writing and debugging incorrect versions helped me fully internalise the idea.