Pseudo-code:

text
function bruteForce(s):
    n = length(s)
    max_len = 0
    for i from 0 to n-1:
        for j from i to n-1:
            if allUnique(s, i, j):
                max_len = max(max_len, j - i + 1)
    return max_len

Complexity Analysis: The time complexity is $O(N^3)$. The nested loops generate $O(N^2)$ substrings, and checking uniqueness for each substring takes $O(N)$ time. Why it fails: With s.length up to $50,000$, an $O(N^3)$ or even an optimized $O(N^2)$ solution will result in a Time Limit Exceeded (TLE) error. We need a linear time solution.

Core Insight for Longest Substring Without Repeating Characters

The brute force method performs redundant checks. If a substring s[i...j] is valid, but s[j+1] is a duplicate of a character at index k (where i <= k <= j), we do not need to check any substrings starting between i and k. Any substring starting in that range and ending at j+1 will still contain the duplicate pair.

The core insight is to maintain a window [left, right] that represents the current substring without repeating characters. As we extend right, if we encounter a character that already exists inside our current window, we must move the left pointer to exclude the previous occurrence of that character.

Instead of incrementing left one by one, we can use a Hash Map to store the last seen index of every character. This allows the left pointer to "jump" directly to index + 1 of the repeated character, instantly restoring the uniqueness property.

Visual Description: Imagine the string as a timeline. The right pointer moves forward, adding characters to the window. When right lands on a character 'A' that was previously seen at index 5, and our current window starts at index 2, the window is now invalid. To fix this, we visualize the left boundary snapping from index 2 to index 6 (5 + 1). This effectively slices off the old 'A' and everything before it, making the new window valid and ready to continue expanding.

Execution Flow

Consider Input: s = "abcabcbb"

1. Init: left = 0, max_len = 0, map = {}.
2. i=0, char='a': 'a' not in map. map = {'a': 0}. max_len = 1. Window: "a".
3. i=1, char='b': 'b' not in map. map = {'a': 0, 'b': 1}. max_len = 2. Window: "ab".
4. i=2, char='c': 'c' not in map. map = {'a': 0, 'b': 1, 'c': 2}. max_len = 3. Window: "abc".
5. i=3, char='a': 'a' is in map (index 0). $0 \ge left (0)$.
   • Move left to $0 + 1 = 1$.
   • Update map for 'a' to 3. map = {'a': 3, ...}.
   • Window size: $3 - 1 + 1 = 3$. stays 3. Window effectively "bca".
6. i=4, char='b': 'b' is in map (index 1). $1 \ge left (1)$.
   • Move left to $1 + 1 = 2$.
   • Update map for 'b' to 4.
7. i=5, char='c': 'c' is in map (index 2). $2 \ge left (2)$.
   • Move left to $2 + 1 = 3$.
   • Update map for 'c' to 5.
8. i=6, char='b': 'b' is in map (index 4). $4 \ge left (3)$.
   • Move left to $4 + 1 = 5$.
   • Update map for 'b' to 6.
9. i=7, char='b': 'b' is in map (index 6). $6 \ge left (5)$.
   • Move left to $6 + 1 = 7$.
   • Update map for 'b' to 7.
10. End: Return max_len = 3.

Proof of Correctness

The algorithm guarantees correctness because it exhaustively checks the longest possible substring ending at every index right. For any ending position right, the optimal starting position left is the smallest index such that s[left...right] has no duplicates. By maintaining left as max(left, prev_index_of_char + 1), we ensure left never moves backward and always skips past the first instance of a duplicate pair. Since we compute the length for every valid right and take the global maximum, the solution is optimal.

Reference Implementation

C++ Solution for LeetCode 3

cpp
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // Map to store the last seen index of each character.
        // Using vector<int> for ASCII optimization (size 256 covers extended ASCII).
        vector<int> charIndex(256, -1);
        
        int left = 0;
        int maxLen = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s[right];
            
            // If character is seen and is inside the current window
            if (charIndex[currentChar] != -1 && charIndex[currentChar] >= left) {
                // Move left pointer to the right of the previous occurrence
                left = charIndex[currentChar] + 1;
            }
            
            // Update the last seen index of the current character
            charIndex[currentChar] = right;
            
            // Update max length
            maxLen = max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
};

Java Solution for LeetCode 3

java
class Solution {
    public int lengthOfLongestSubstring(String s) {
        // Map to store character and its most recent index
        Map<Character, Integer> map = new HashMap<>();
        
        int left = 0;
        int maxLen = 0;
        
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);
            
            // If duplicate found within the current window
            if (map.containsKey(currentChar)) {
                // Move left pointer, but ensure it never moves backward
                // Math.max is crucial here
                left = Math.max(left, map.get(currentChar) + 1);
            }
            
            // Update the map with the current index
            map.put(currentChar, right);
            
            // Calculate current window length and update max
            maxLen = Math.max(maxLen, right - left + 1);
        }
        
        return maxLen;
    }
}

Python Solution for LeetCode 3

python
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Dictionary to store the last seen index of characters
        char_index_map = {}
        
        left = 0
        max_len = 0
        
        for right in range(len(s)):
            current_char = s[right]
            
            # If the character is already in the map and is part of the current window
            if current_char in char_index_map and char_index_map[current_char] >= left:
                # Move the left pointer to the right of the previous occurrence
                left = char_index_map[current_char] + 1
            
            # Update the last seen index
            char_index_map[current_char] = right
            
            # Update the maximum length found so far
            max_len = max(max_len, right - left + 1)
            
        return max_len