Longest Substring Without Repeating Characters

Master this topic with zero to advance depth.

Longest Substring Without Repeating Characters

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

Visual Representation

s = "abcabcbb"

L  R
|  |
a b c a b c b b
[---]             Set: {a, b, c}, Len: 3

   L  R
   |  |
a b c a b c b b
   [---]          Set: {b, c, a}, Len: 3

Medium

Examples

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

Approach 1

Level I: Brute Force

Intuition

Check every possible substring and verify if it contains unique characters. A string of length $N$ has $O(N^2)$ substrings. Checking each takes $O(N)$ , leading to $O(N^3)$ . We can optimize the check using a Set to $O(N^2)$ .

Thought Process

Use two nested loops to define every potential substring s[i...j].
For each substring, use a third loop or a Set to check for duplicates.
If no duplicates, update the maxLength.

⏱ O(N^2)💾 O(min(N, M)) where M is alphabet size.

Detailed Dry Run

i	j	Substring	Unique?	Max Len
0	0	"a"	Yes	1
0	1	"ab"	Yes	2
0	2	"abc"	Yes	3
0	3	"abca"	No	3
1	3	"bca"	Yes	3

java

import java.util.*;

public class Main {
    public static int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                if (isUnique(s, i, j)) {
                    res = Math.max(res, j - i + 1);
                }
            }
        }
        return res;
    }

    private static boolean isUnique(String s, int start, int end) {
        Set<Character> chars = new HashSet<>();
        for (int k = start; k <= end; k++) {
            if (chars.contains(s.charAt(k))) return false;
            chars.add(s.charAt(k));
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
    }
}

Approach 2

Level II: Binary Search on Answer (O(N log N))

Intuition

We can binary search for the maximum length k. For a fixed k, we check if there exists any substring of length k with no repeating characters using a fixed-size sliding window. If a valid substring of length k exists, then any length smaller than k is also possible, so we search in [k, right]. Otherwise, we search in [left, k-1].

Thought Process

Search range for maximum length is [1, n].
In each step of binary search (length mid):
- Use a sliding window of size mid to check for uniqueness.
- If unique substring found, ans = mid, low = mid + 1.
- Else, high = mid - 1.

Pattern: Search on Answer Space

⏱ O(N log N) - Binary search takes $\log N$ steps, each check takes $O(N)$.💾 O(min(N, M)) for the character set during the check.

java

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.isEmpty()) return 0;
        int low = 1, high = s.length(), ans = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (hasUnique(s, mid)) {
                ans = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return ans;
    }

    private boolean hasUnique(String s, int k) {
        java.util.Map<Character, Integer> window = new java.util.HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            window.put(c, window.getOrDefault(c, 0) + 1);
            if (i >= k) {
                char out = s.charAt(i - k);
                window.put(out, window.get(out) - 1);
                if (window.get(out) == 0) window.remove(out);
            }
            if (window.size() == k) return true;
        }
        return false;
    }
}

Approach 3

Level III: Optimal (Sliding Window)

Intuition

Categorization

This is a Variable Size Window problem because the length of the unique substring changes as we encounter duplicates.

Thought Process

Instead of checking all substrings, we maintain a sliding window [left, right]. As we expand right, we add the character to a Set. If s[right] is already in the Set, we have a violation. We must shrink the window from the left until the duplicate is gone.

Mandatory Variables

left: Marks the start of the current unique substring.
charSet: Stores characters in the current window for $O(1)$ duplicate checking.
maxLength: Tracks the largest window size found.

⏱ O(N)💾 O(min(N, M)) where M is the character set size.

Detailed Dry Run

Step	L	R	Char	Action	Set Content	Max Len
1	0	0	'a'	Add 'a'	{a}	1
2	0	1	'b'	Add 'b'	{a, b}	2
3	0	2	'c'	Add 'c'	{a, b, c}	3
4	0	3	'a'	Dupe 'a'! Shrink L	{b, c, a}	3
5	1	4	'b'	Dupe 'b'! Shrink L	{c, a, b}	3

java

import java.util.*;

public class Main {
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<>();
        int left = 0, maxLength = 0;
        for (int right = 0; right < s.length(); right++) {
            // Shrink if duplicate found
            while (set.contains(s.charAt(right))) {
                set.remove(s.charAt(left));
                left++;
            }
            // Expand
            set.add(s.charAt(right));
            // Update Result
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("abcabcbb")); // 3
    }
}

⚠️ Common Pitfalls & Tips

Be careful with the window shrink condition. It must be a while loop to remove all characters until the duplicate is gone. Also, remember to add the current character after the shrink loop.

← Previous QuestionMinimum Size Subarray Sum

Next Question →Permutation in String

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.