Longest Substring Without Repeating Characters

The Longest Substring Without Repeating Characters problem is one of those warm-up problems that seems deceptively simple but teaches you a ton about sliding window techniques and string manipulation. It shows up frequently in interviews and also mimics real-world cases like processing tokens or user input where uniqueness matters.

Problem Statement

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

Example 1:

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

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.

1. Clarify Requirements Before Jumping Into Code

We’re given a string, and we need to return the length of the longest substring that doesn’t have repeating characters.

• Substring means contiguous characters.

• We don’t need to return the substring itself, just its length.

• Empty string should return 0.

• String can include any printable ASCII characters, not just letters.

2. Identify the Category of the Question

This is a sliding window problem.

Patterns involved:

• Sliding Window

• HashSet or HashMap for tracking elements inside the window

• Two pointers (start and end) that expand and contract the window as we iterate

These problems often deal with substrings, sequences, or contiguous intervals where a constraint must be maintained (like uniqueness in this case).

3. Consider a Brute‑Force Approach to Understand the Problem

The brute-force solution here is try all substrings, and check every substring for unique characters.

• For each start index, try all possible end indices.

• Check if the substring from start to end has any repeating characters.

Time complexity: O(n³)

• O(n²) to check all possible substrings

• O(n) to check uniqueness in each substring

That's way too slow!

4. Brainstorm More Solutions

Let's try thinking about this another way.

If I think of this problem as one where I'm looking for the largest possible "window" of elements, then what are the possible ways that I can change that window?

1. I can expand the window to include new characters.

2. If by expanding the window to add a new character, I've found a duplicate, than naturally I'd want to shrink the window. I want to try and remove the duplicate. But I don't want to shrink from the right, because that's just retesting windows I've already looked at. So instead, let's shrink the window from the left to try until we've ditched the duplicates!

This pattern is often referred to a sliding window! It's very similar to two-pointer problems, only within a sliding window, the focus is on the elements within the window, as oppposed to the two pointers themselves.

The question then becomes: How do I quickly detect duplicates in my window? I want to do it in constant time so that I'm not adding to my time complexity.

The answer? A hash set!

Putting it all together:

• Use a Set to store characters currently in the window.

• Two pointers: left and right, starting at elements 0 and 1

• Move the right pointer to the right and add characters to the HashSet until a duplicate is found.

• When a duplicate is found, remove characters from the left until the duplicate is gone.

• Keep track of the max window size.
  

This gives us a linear O(n) solution because each character is added and removed from the set at most once.

We can't really get any better than O(n) time, and this solution is very clean and straigh forward, so let's go with it!

5. Discuss Trade‑Offs Between Your Solutions

Approach	Time Complexity	Space Complexity	Pros	Cons
Brute-force	O(n³)	O(n)	Simple to understand	Very slow, impractical
Sliding Window with Set	O(n)	O(min(n, a))	Fast, clean, real-time sliding	May have unnecessary steps

6. Write Pseudocode to Structure Your Thoughts

initialize set
left = 0, maxLen = 0

for right from 0 to end of string:
    while character at right is in set:
        remove character at left from set
        increment left
    add character at right to set
    maxLen = max(maxLen, right - left + 1)

return maxLen

7. Consider Edge Cases

• Empty string → return 0

• All repeating characters → length is 1

• All unique characters → return full length

• Mix of repeat and unique characters

Make sure duplicate characters are handled precisely (e.g. repeated at different intervals).

8. Write Full Code Syntax (Java)

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

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

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

        return maxLen;
    }
}

9. Test Your Code

System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
System.out.println(lengthOfLongestSubstring("bbbbb"));    // 1
System.out.println(lengthOfLongestSubstring("pwwkew"));   // 3
System.out.println(lengthOfLongestSubstring(""));         // 0
System.out.println(lengthOfLongestSubstring("abcdef"));   // 6
System.out.println(lengthOfLongestSubstring("abba"));     // 2

10. Key Lessons to Remember for Future Questions

• Sliding window is powerful when the problem asks for a contiguous subsequence with certain constraints.

• Use a Set when you need to check for uniqueness in constant time.

• Be careful with when to shrink the window, especially around off-by-one bugs.

• Memorizing this pattern pays off — it comes up in many forms, like longest repeating character replacement, minimum window substring, etc.

Good Luck and Happy Coding!