Data Structures & Algorithms (Sliding Window): Longest Substring Without Repeating Characters

February 2, 2026

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

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3. Note that "bca" and "cab" are also correct answers.

Example 2:

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

Example 3:

Input: s = "abba"
Output: 2
Explanation: The answer is "ab", with the length of 2.

Solve Here: Leetcode 3

Approach 1: Nested Loops

Use nested loops to explore longest possible substring starting from each character.

Algorithm

1. Initialize maxLength to 0 to keep track of the longest substring found so far.
2. Iterate over each character in the string using an outer loop. The current index represents the starting position 
of the substring. For each starting position:

    4. Initialize an empty HashSet to store the characters in the current substring.
    5. Initialize currLength to 0.

    6. Iterate from the current starting position toward the end of the string using an inner loop. For each character:
        7. If the character is not present in the HashSet, add it to the set and increment currLength.
        8. If the character is already present in the HashSet, stop the inner loop because extending the substring 
        would introduce a duplicate.
    
    9. Update maxLength with the maximum of maxLength and currLength.

8. Return maxLength.

Implementation

Sample inputs
1public int lengthOfLongestSubstring(String s) {
2 int maxLength = 0;
3 for (int i = 0; i < s.length(); i++) {
4 Set<Character> unique = new HashSet<>();
5 int currLength = 0;
6 for (int j = i; j < s.length(); j++) {
7 char ch = s.charAt(j);
8 if (!unique.contains(ch)) {
9 unique.add(ch);
10 currLength++;
11 maxLength = Math.max(maxLength, currLength);
12 } else {
13 break;
14 }
15 }
16 }
17 return maxLength;
18}
Ready

Press Play or Step to explore every starting index and see the window grow until a repeat hits.

Input string
j
j
j
j
j
j
j
j
a
b
c
a
b
c
b
b
i
i
i
i
i
i
i
i
0
1
2
3
4
5
6
7
HashSet
empty
unique.contains('x')→?
placeholder
i= —
j= —
currLength= 0
maxLength= 0
Longest substring0
0/93

Time Complexity

In the worst-case scenario (all characters in the input string are unique), for every starting index i, we explore all (n-i) characters to its right.

This results in a total of: n + (n-1) + ... + 2 + 1 = n(n+1)/2 iterations of the inner loop across all starting indices. Therefore, the overall time complexity is O(n²).

Space Complexity

In the worst case (when all characters are unique), the HashSet can grow to hold at most n characters at a time. Therefore, the overall space complexity = O(n).

Key Observation

While expanding a substring, if we encounter a character that has already been seen, we can directly move the starting index i to the position right after the previous occurrence of that character.

All starting indices before that would only produce smaller substrings.

key-observations

Note

A character is only considered duplicate only if its previous occurrence lies within the current window. If it appears before the current starting index, it can be safely ignored.

key-observations

Approach 2: Two Pointers

Use two pointers (left, right) to traverse the string while maintaining a sliding window. Maintain a HashMap to store the last seen index of each character. This allows you to efficiently jump left forward to (lastSeenIndex + 1).

Algorithm

1. Initialize left to 0 to represent the start of the current window.
2. Initialize maxLength to 0 to keep track of the longest valid substring found so far.
3. Initialize a HashMap called lastSeen to store the most recent index of each character.

4. Iterate through the string using right as the end of the current window. For each character:
    5. If the character exists in lastSeen and its previous occurrence is inside the current window, 
    move left to one position after that previous occurrence.
    6. Update lastSeen with the current index of the character.
    7. Calculate the current window length as right - left + 1.
    8. Update maxLength.

9. Return maxLength.

Implementation

Sample inputs
1public int lengthOfLongestSubstring(String s) {
2 int maxLength = 0;
3 Map<Character, Integer> lastSeen = new HashMap<>();
4 int left = 0;
5 for (int right = 0; right < s.length(); right++) {
6 char ch = s.charAt(right);
7 if (lastSeen.containsKey(ch) && lastSeen.get(ch) >= left) {
8 left = lastSeen.get(ch) + 1;
9 }
10 lastSeen.put(ch, right);
11 maxLength = Math.max(maxLength, right - left + 1);
12 }
13 return maxLength;
14}
Ready

Press Play or Step. The right pointer expands; a duplicate inside the window jumps left forward.

Input string
R
R
R
R
R
R
R
R
a
b
c
a
b
c
b
b
L
L
L
L
L
L
L
L
0
1
2
3
4
5
6
7
lastSeen
empty
lastSeen.containsKey('x') && lastSeen.get('x') ≥ left
placeholder
left= 0
right= —
window= —
maxLength= 0
Longest substring0
0/39

Time Complexity

Each character is visited at most twice, once when the right pointer expands the window and once when the left pointer shrinks it.

Since both pointers traverse the string at most n times, the overall time complexity = O(n).

Space Complexity

The HashMap stores the last seen index of each unique character. In the worst case (when all characters are distinct), it can hold up to n entries.

Therefore, the overall space complexity = O(n).