Skip to main content
CodePeetCodePeet
CodePeet 250

Longest Substring Without Repeating Characters

MEDIUMProblemSolveExternal Links

Description

You are given a string s. Your task is to find the length of the longest contiguous sequence of characters (substring) that contains no duplicate characters.

A substring is a continuous part of the string. For example, in the string "abcde", the substrings include "a", "ab", "abc", "bcd", "cde", and so on. Note that "ace" is NOT a substring because the characters are not consecutive in the original string (that would be called a subsequence).

A substring has no repeating characters when every character in it appears exactly once. For instance, "abc" has no repeating characters, but "aba" does because 'a' appears twice.

Your goal is to find the maximum length among all such valid substrings.

Examples

Example 1

Input: s = "abcabcbb"

Output: 3

Explanation: Let's examine the substrings without repeating characters:

  • Starting at index 0: "a" (length 1), "ab" (length 2), "abc" (length 3). We stop here because the next character 'a' at index 3 would repeat.
  • Starting at index 1: "b", "bc", "bca" (length 3). We stop because 'b' at index 4 repeats.
  • Starting at index 2: "c", "ca", "cab" (length 3). We stop because 'c' at index 5 repeats.

The longest substrings without repeating characters are "abc", "bca", and "cab", all with length 3. Therefore, the answer is 3.

Example 2

Input: s = "bbbbb"

Output: 1

Explanation: Every character in this string is 'b'. Any substring longer than 1 character would contain duplicate 'b' characters. The only valid substrings are single characters: "b". Therefore, the maximum length is 1.

Example 3

Input: s = "pwwkew"

Output: 3

Explanation: Let's trace through:

  • "p" → valid (length 1)
  • "pw" → valid (length 2)
  • "pww" → invalid (w repeats)
  • Starting fresh from second 'w': "w", "wk", "wke" (length 3)
  • "wkew" → invalid (w repeats)
  • "kew" → valid (length 3)

The longest valid substrings are "wke" and "kew", both with length 3. Note that "pwke" is NOT valid because it's a subsequence (skipping the second 'w'), not a substring.

Example 4

Input: s = ""

Output: 0

Explanation: The string is empty, so there are no characters to form any substring. The answer is 0.

Constraints

  • 0 ≤ s.length ≤ 5 × 10^4
  • s consists of English letters (both uppercase and lowercase), digits, symbols, and spaces
  • The character set includes all printable ASCII characters (up to 128 unique characters)

Editorial

Brute Force

Intuition

The most straightforward approach is to consider every possible substring of the given string and check whether it contains all unique characters. If it does, we compare its length with our current maximum and update accordingly.

Think of it like this: if you were asked to find the longest word in a book where no letter repeats, you would go through every possible word (every starting and ending position), check each one for duplicate letters, and keep track of the longest valid one you find.

To generate all substrings, we need two pointers:

  1. A starting position (let's call it i) that goes from the beginning to the end
  2. An ending position (let's call it j) that starts from i and extends to the end

For each substring from position i to position j, we need to verify that all characters within it are unique. We can do this by scanning through the substring and using a data structure to track which characters we've already seen.

Step-by-Step Explanation

Let's trace through with s = "abcabcbb":

Step 1: Initialize max_length = 0

Step 2: Start with i = 0 (first character 'a')

  • j = 0: substring = "a", check uniqueness → all unique, length = 1, max_length = 1
  • j = 1: substring = "ab", check uniqueness → all unique, length = 2, max_length = 2
  • j = 2: substring = "abc", check uniqueness → all unique, length = 3, max_length = 3
  • j = 3: substring = "abca", check uniqueness → 'a' repeats! Not valid.
  • j = 4: substring = "abcab", check uniqueness → 'a' and 'b' repeat! Not valid.
  • (continue checking remaining j values, none valid for this i)

Step 3: Move to i = 1 (character 'b')

  • j = 1: substring = "b", all unique, length = 1, max_length stays 3
  • j = 2: substring = "bc", all unique, length = 2
  • j = 3: substring = "bca", all unique, length = 3, max_length stays 3
  • j = 4: substring = "bcab", 'b' repeats! Not valid.

Step 4: Continue this process for all starting positions i = 2, 3, 4, 5, 6, 7

Each time we find a valid substring, we update max_length if the current length is greater.

Final max_length = 3

Algorithm

  1. Initialize max_length to 0
  2. For each starting position i from 0 to n-1:
    • For each ending position j from i to n-1:
      • Extract the substring from index i to j
      • Check if all characters in this substring are unique:
        • Use a set or array to track seen characters
        • Iterate through the substring
        • If any character is already in the set, substring is invalid
        • Otherwise, add character to set
      • If substring is valid and its length > max_length, update max_length
  3. Return max_length

Code

#include <string>
#include <unordered_set>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int maxLength = 0;
        
        // Try every possible starting position
        for (int i = 0; i < n; i++) {
            // Try every possible ending position
            for (int j = i; j < n; j++) {
                // Check if substring s[i..j] has all unique characters
                if (hasAllUniqueChars(s, i, j)) {
                    maxLength = max(maxLength, j - i + 1);
                }
            }
        }
        
        return maxLength;
    }
    
private:
    bool hasAllUniqueChars(const string& s, int start, int end) {
        unordered_set<char> seen;
        
        for (int k = start; k <= end; k++) {
            // If character already exists in set, not all unique
            if (seen.count(s[k]) > 0) {
                return false;
            }
            seen.insert(s[k]);
        }
        
        return true;
    }
};
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        max_length = 0
        
        # Try every possible starting position
        for i in range(n):
            # Try every possible ending position
            for j in range(i, n):
                # Check if substring s[i:j+1] has all unique characters
                if self.has_all_unique_chars(s, i, j):
                    max_length = max(max_length, j - i + 1)
        
        return max_length
    
    def has_all_unique_chars(self, s: str, start: int, end: int) -> bool:
        seen = set()
        
        for k in range(start, end + 1):
            # If character already exists in set, not all unique
            if s[k] in seen:
                return False
            seen.add(s[k])
        
        return True
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLength = 0;
        
        // Try every possible starting position
        for (int i = 0; i < n; i++) {
            // Try every possible ending position
            for (int j = i; j < n; j++) {
                // Check if substring s[i..j] has all unique characters
                if (hasAllUniqueChars(s, i, j)) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }
        
        return maxLength;
    }
    
    private boolean hasAllUniqueChars(String s, int start, int end) {
        Set<Character> seen = new HashSet<>();
        
        for (int k = start; k <= end; k++) {
            char c = s.charAt(k);
            // If character already exists in set, not all unique
            if (seen.contains(c)) {
                return false;
            }
            seen.add(c);
        }
        
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n³)

We have three nested operations:

  1. The outer loop runs n times (for each starting position i)
  2. The inner loop runs up to n times (for each ending position j)
  3. The uniqueness check scans up to n characters for each substring

This gives us n × n × n = n³ operations in the worst case. For a string of length 50,000, this would be 125 trillion operations, which is far too slow.

Space Complexity: O(min(n, m))

Where m is the size of the character set (128 for ASCII). The set used to check for duplicates can contain at most min(n, m) characters. In the worst case with all unique characters, the set holds all n characters or the entire character set, whichever is smaller.

Why This Approach Is Not Efficient

The brute force approach has O(n³) time complexity, which is extremely slow for the given constraints. With n up to 5 × 10^4, we would need up to 1.25 × 10^14 operations. Even at a billion operations per second, this would take over a day to complete!

The main inefficiency comes from two sources:

  1. Redundant substring generation: We're generating all possible substrings, but many of them are unnecessary. If we've already found that "abca" has a duplicate, we don't need to check "abcab", "abcabc", etc., because they all contain the same duplicate.

  2. Repeated character checking: For each substring, we're scanning through all its characters to check for duplicates. We're doing the same work over and over — when we check "ab" and then "abc", we're re-verifying that 'a' and 'b' don't repeat.

We need an approach that:

  • Avoids checking substrings that we already know are invalid
  • Builds upon previous work instead of starting fresh each time

This leads us to the idea of maintaining a "window" that we can efficiently expand and shrink.

Better Approach - Optimized Brute Force

Intuition

Instead of checking each substring from scratch, we can be smarter about it. The key insight is: if we're extending a valid substring by one character, we only need to check if the new character already exists in our current substring — we don't need to re-verify the entire thing.

Think of it like building a tower of unique blocks:

  • You start with one block
  • You try to add the next block, but first check if you already have that color
  • If you do have that color, you stop this tower and start a new one from the next position
  • If you don't have that color, add it and continue

For each starting position, we extend as far as possible until we hit a duplicate. We use a set to keep track of characters in our current substring, adding new characters as we go and stopping immediately when we find a duplicate.

This eliminates the innermost loop of checking all characters for each substring.

Step-by-Step Explanation

Let's trace through with s = "abcabcbb":

Step 1: Initialize max_length = 0

Step 2: Start with i = 0

  • Create empty set: seen = {}
  • j = 0: s[0] = 'a', not in seen → add 'a', seen = {'a'}, length = 1, max_length = 1
  • j = 1: s[1] = 'b', not in seen → add 'b', seen = {'a','b'}, length = 2, max_length = 2
  • j = 2: s[2] = 'c', not in seen → add 'c', seen = {'a','b','c'}, length = 3, max_length = 3
  • j = 3: s[3] = 'a', ALREADY in seen → STOP extending, move to next i

Step 3: i = 1

  • Create empty set: seen = {}
  • j = 1: s[1] = 'b', not in seen → add 'b', seen = {'b'}, length = 1
  • j = 2: s[2] = 'c', not in seen → add 'c', seen = {'b','c'}, length = 2
  • j = 3: s[3] = 'a', not in seen → add 'a', seen = {'b','c','a'}, length = 3, max_length stays 3
  • j = 4: s[4] = 'b', ALREADY in seen → STOP extending

Step 4: Continue for i = 2, 3, 4, 5, 6, 7...

We still check all starting positions, but for each starting position, we stop as soon as we hit a duplicate instead of continuing to check longer substrings.

Algorithm

  1. Initialize max_length to 0
  2. For each starting position i from 0 to n-1:
    • Create an empty set seen to track characters in current substring
    • For each position j from i to n-1:
      • If s[j] is already in seen:
        • Break out of inner loop (can't extend further from this start)
      • Otherwise:
        • Add s[j] to seen
        • Update max_length = max(max_length, j - i + 1)
  3. Return max_length

Code

#include <string>
#include <unordered_set>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int maxLength = 0;
        
        // Try every possible starting position
        for (int i = 0; i < n; i++) {
            unordered_set<char> seen;
            
            // Extend from position i as far as possible
            for (int j = i; j < n; j++) {
                // If we've seen this character before, stop extending
                if (seen.count(s[j]) > 0) {
                    break;
                }
                
                // Add character to our current window
                seen.insert(s[j]);
                
                // Update maximum length
                maxLength = max(maxLength, j - i + 1);
            }
        }
        
        return maxLength;
    }
};
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        max_length = 0
        
        # Try every possible starting position
        for i in range(n):
            seen = set()
            
            # Extend from position i as far as possible
            for j in range(i, n):
                # If we've seen this character before, stop extending
                if s[j] in seen:
                    break
                
                # Add character to our current window
                seen.add(s[j])
                
                # Update maximum length
                max_length = max(max_length, j - i + 1)
        
        return max_length
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLength = 0;
        
        // Try every possible starting position
        for (int i = 0; i < n; i++) {
            Set<Character> seen = new HashSet<>();
            
            // Extend from position i as far as possible
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                
                // If we've seen this character before, stop extending
                if (seen.contains(c)) {
                    break;
                }
                
                // Add character to our current window
                seen.add(c);
                
                // Update maximum length
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }
        
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times. The inner loop, in the worst case (all unique characters), also runs n times. However, we've eliminated the third nested loop for uniqueness checking — now we check in O(1) time using a hash set.

Total: n × n = O(n²)

For n = 50,000, this is about 2.5 billion operations, which is still too slow but significantly better than the O(n³) brute force.

Space Complexity: O(min(n, m))

Where m is the size of the character set (128 for ASCII). For each starting position, we create a new set that can hold at most min(n, m) characters. The set is recreated for each starting position, so we only use one set at a time.

Why This Approach Is Not Efficient

While the optimized brute force is better than the naive O(n³) approach, it's still O(n²), which is too slow for strings up to 50,000 characters. At 2.5 billion operations, this would take several seconds even on fast hardware.

The key inefficiency is that we're throwing away useful information when we move to the next starting position. Consider this example:

String: a b c d e f c g h
Index:  0 1 2 3 4 5 6 7 8

When starting from i=0, we find that "abcdef" is valid but "abcdefc" is not (because 'c' repeats).

When we move to i=1, we start completely fresh and check "bcdef" → "bcdefc" → fails at 'c' again.

But wait — we already know that the substring "bcdef" (indices 1-5) is valid from our previous iteration! We're doing redundant work.

The insight is: instead of restarting from scratch, can we "slide" our window? When we encounter a duplicate, instead of moving the start by just 1 and re-checking everything, we could move the start just past the previous occurrence of the duplicate character.

This leads us to the sliding window technique.

Better Approach - Sliding Window with Set

Intuition

The sliding window technique is perfect for this problem. Instead of checking all substrings starting from each position, we maintain a "window" of characters that we know is valid (contains no duplicates).

Imagine you have a stretchy window frame that you're sliding across the string:

  • The right edge of the window keeps moving forward, adding new characters
  • When you encounter a character that's already in your window, you shrink the window from the left until the duplicate is removed
  • At each step, you record the window size if it's the largest you've seen

This works because:

  1. We only need to find the LENGTH of the longest valid substring, not the substring itself
  2. Once a character causes a duplicate, we must remove either it or its previous occurrence
  3. By always removing from the left, we ensure we've considered all valid substrings ending at the current position

Key insight: Both pointers only move forward, never backward. The left pointer moves forward to remove characters, and the right pointer moves forward to add characters. This guarantees O(n) time because each character is visited at most twice (once by each pointer).

Step-by-Step Explanation

Let's trace through with s = "pwwkew":

We maintain: left pointer, right pointer, a set of characters in current window, and max_length.

Initial State: left = 0, right = 0, seen = {}, max_length = 0

Step 1: right = 0, s[0] = 'p'. 'p' not in seen → add 'p'. seen = {'p'}, window = "p", length = 1, max_length = 1.

Step 2: right = 1, s[1] = 'w'. 'w' not in seen → add 'w'. seen = {'p','w'}, window = "pw", length = 2, max_length = 2.

Step 3: right = 2, s[2] = 'w'. 'w' IS in seen! Shrink from left: remove s[0]='p', left=1. 'w' still in seen. Remove s[1]='w', left=2. Now 'w' not in seen → add 'w'. seen = {'w'}, window = "w", length = 1, max_length = 2.

Step 4: right = 3, s[3] = 'k'. 'k' not in seen → add 'k'. seen = {'w','k'}, window = "wk", length = 2, max_length = 2.

Step 5: right = 4, s[4] = 'e'. 'e' not in seen → add 'e'. seen = {'w','k','e'}, window = "wke", length = 3, max_length = 3.

Step 6: right = 5, s[5] = 'w'. 'w' IS in seen! Shrink from left: remove s[2]='w', left=3. Now 'w' not in seen → add 'w'. seen = {'k','e','w'}, window = "kew", length = 3, max_length = 3.

Final Answer: max_length = 3

Sliding Window with Set — Expand and Shrink — Watch how the window expands to the right adding characters to a set, and shrinks from the left when a duplicate is encountered, always maintaining a window of unique characters.

Algorithm

  1. Initialize left = 0 (left edge of window)
  2. Initialize seen = empty set (characters in current window)
  3. Initialize max_length = 0
  4. For each right from 0 to n-1:
    • While s[right] is already in seen:
      • Remove s[left] from seen
      • Increment left
    • Add s[right] to seen
    • Update max_length = max(max_length, right - left + 1)
  5. Return max_length

Code

#include <string>
#include <unordered_set>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int maxLength = 0;
        int left = 0;
        unordered_set<char> seen;
        
        // right pointer scans through the string
        for (int right = 0; right < n; right++) {
            // If character at right is already in window,
            // shrink window from left until it's removed
            while (seen.count(s[right]) > 0) {
                seen.erase(s[left]);
                left++;
            }
            
            // Add current character to window
            seen.insert(s[right]);
            
            // Update maximum length
            maxLength = max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
};
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        max_length = 0
        left = 0
        seen = set()
        
        # right pointer scans through the string
        for right in range(n):
            # If character at right is already in window,
            # shrink window from left until it's removed
            while s[right] in seen:
                seen.remove(s[left])
                left += 1
            
            # Add current character to window
            seen.add(s[right])
            
            # Update maximum length
            max_length = max(max_length, right - left + 1)
        
        return max_length
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLength = 0;
        int left = 0;
        Set<Character> seen = new HashSet<>();
        
        // right pointer scans through the string
        for (int right = 0; right < n; right++) {
            char c = s.charAt(right);
            
            // If character at right is already in window,
            // shrink window from left until it's removed
            while (seen.contains(c)) {
                seen.remove(s.charAt(left));
                left++;
            }
            
            // Add current character to window
            seen.add(c);
            
            // Update maximum length
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: O(n)

At first glance, you might think this is O(n²) because of the while loop inside the for loop. However, let's analyze more carefully:

  • The right pointer moves from 0 to n-1, visiting each index exactly once.
  • The left pointer also moves from 0 to at most n-1, and it only ever increases (never goes backward).
  • Each character in the string is added to the set exactly once (when right reaches it) and removed from the set at most once (when left passes it).

So the total number of operations is at most 2n: each character is processed at most twice (once for addition, once for removal). This gives us O(2n) = O(n) time complexity.

Space Complexity: O(min(n, m))

Where m is the size of the character set. The set seen can contain at most min(n, m) characters:

  • If n < m: we can have at most n unique characters
  • If n ≥ m: we can have at most m unique characters (the entire character set)

For ASCII characters (m = 128), this is O(min(n, 128)) = O(1) in practice. For Unicode, m could be much larger.

Why This Approach Is Not Efficient

Wait — isn't O(n) already optimal? In terms of time complexity, yes! We must look at each character at least once, so O(n) is the theoretical minimum.

However, there's still room for improvement in terms of constant factors. Look at our sliding window solution:

When we encounter a duplicate character, we shrink from the left one character at a time until the duplicate is removed. For example:

String: a b c d e b x y z
        0 1 2 3 4 5 6 7 8

When right = 5 (second 'b'), we find 'b' is in our window at index 1. We then:

  1. Remove 'a' at index 0, left = 1, 'b' still in seen
  2. Remove 'b' at index 1, left = 2, now we can proceed

We removed 'a' unnecessarily! If we knew that the previous 'b' was at index 1, we could have jumped directly to left = 2.

This insight leads us to an even more optimized approach that uses a hash map to track the last position of each character.

Optimal Approach - Sliding Window with Hash Map

Intuition

The previous sliding window approach is already O(n), but we can make it more elegant and potentially faster in practice by avoiding unnecessary left pointer movements.

Instead of using a set to track which characters are in our window, we use a hash map (dictionary) to store the most recent index of each character. When we encounter a duplicate:

  1. We look up where that character last appeared
  2. We immediately jump our left pointer to one position after that last occurrence
  3. No need to incrementally remove characters one by one

Think of it like this: if you're reading a book and find that a word you just read appeared earlier in your current paragraph, instead of going back word-by-word to find it, you just look it up in an index that tells you exactly where it was.

There's one subtlety: when we look up a character's last position, that position might be BEFORE our current window's left boundary. In that case, the duplicate is not actually in our window, so we shouldn't move the left pointer backward. We handle this by taking the maximum of the current left position and (last occurrence + 1).

Step-by-Step Explanation

Let's trace through with s = "pwwkew":

We maintain: left pointer, a hash map storing last index of each character, and max_length.

Initial State: left = 0, lastIndex = {}, max_length = 0

Step 1: right = 0, s[0] = 'p'. 'p' not in lastIndex. Window length = 0 - 0 + 1 = 1, max_length = 1. Set lastIndex['p'] = 0.

Step 2: right = 1, s[1] = 'w'. 'w' not in lastIndex. Window length = 1 - 0 + 1 = 2, max_length = 2. Set lastIndex['w'] = 1.

Step 3: right = 2, s[2] = 'w'. 'w' IS in lastIndex at position 1, and 1 ≥ left (0). Jump left to lastIndex['w'] + 1 = 2. Window length = 2 - 2 + 1 = 1, max_length stays 2. Update lastIndex['w'] = 2.

Step 4: right = 3, s[3] = 'k'. 'k' not in lastIndex. Window length = 3 - 2 + 1 = 2, max_length stays 2. Set lastIndex['k'] = 3.

Step 5: right = 4, s[4] = 'e'. 'e' not in lastIndex. Window length = 4 - 2 + 1 = 3, max_length = 3. Set lastIndex['e'] = 4.

Step 6: right = 5, s[5] = 'w'. 'w' IS in lastIndex at position 2, and 2 ≥ left (2). Jump left to lastIndex['w'] + 1 = 3. Window length = 5 - 3 + 1 = 3, max_length stays 3. Update lastIndex['w'] = 5.

Final Answer: max_length = 3

Sliding Window with Hash Map — Direct Jump on Duplicate — Watch how the hash map stores each character's last seen index, allowing the left pointer to jump directly past duplicates instead of shrinking one character at a time.

Algorithm

  1. Initialize left = 0 (left edge of window)
  2. Initialize lastIndex = empty hash map (maps character → most recent index)
  3. Initialize max_length = 0
  4. For each right from 0 to n-1:
    • If s[right] exists in lastIndex AND lastIndex[s[right]] >= left:
      • Jump left to lastIndex[s[right]] + 1 (skip past the duplicate)
    • Update max_length = max(max_length, right - left + 1)
    • Update lastIndex[s[right]] = right
  5. Return max_length

Code

#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.length();
        int maxLength = 0;
        int left = 0;
        unordered_map<char, int> lastIndex;
        
        for (int right = 0; right < n; right++) {
            char c = s[right];
            
            // If character was seen before and is within current window
            if (lastIndex.count(c) > 0 && lastIndex[c] >= left) {
                // Jump left pointer past the previous occurrence
                left = lastIndex[c] + 1;
            }
            
            // Update maximum length
            maxLength = max(maxLength, right - left + 1);
            
            // Record current position of this character
            lastIndex[c] = right;
        }
        
        return maxLength;
    }
};
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        max_length = 0
        left = 0
        last_index = {}  # Maps character to its most recent index
        
        for right in range(n):
            c = s[right]
            
            # If character was seen before and is within current window
            if c in last_index and last_index[c] >= left:
                # Jump left pointer past the previous occurrence
                left = last_index[c] + 1
            
            # Update maximum length
            max_length = max(max_length, right - left + 1)
            
            # Record current position of this character
            last_index[c] = right
        
        return max_length
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length();
        int maxLength = 0;
        int left = 0;
        Map<Character, Integer> lastIndex = new HashMap<>();
        
        for (int right = 0; right < n; right++) {
            char c = s.charAt(right);
            
            // If character was seen before and is within current window
            if (lastIndex.containsKey(c) && lastIndex.get(c) >= left) {
                // Jump left pointer past the previous occurrence
                left = lastIndex.get(c) + 1;
            }
            
            // Update maximum length
            maxLength = Math.max(maxLength, right - left + 1);
            
            // Record current position of this character
            lastIndex.put(c, right);
        }
        
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: O(n)

We iterate through the string exactly once with the right pointer. For each character:

  • Hash map lookup: O(1) average
  • Hash map insertion: O(1) average
  • All other operations: O(1)

Unlike the previous sliding window approach where the left pointer might need to move multiple times for a single right pointer position, here the left pointer only makes one "jump" per duplicate encounter. The total number of operations is exactly n iterations with O(1) work each.

Space Complexity: O(min(n, m))

Where m is the size of the character set. The hash map stores at most one entry per unique character. Since we're storing indices (not just presence), we could have up to:

  • n entries if all characters are unique and n ≤ m
  • m entries if the string is longer than the character set size

For the given constraints (ASCII characters including letters, digits, symbols, spaces), m ≈ 128, so this is effectively O(1) constant space.

Comparison with Previous Approach:
Both approaches are O(n) time and O(min(n, m)) space. However, this version is often faster in practice because:

  1. We never remove elements from our data structure
  2. Each character is processed exactly once (not potentially twice)
  3. The left pointer makes direct jumps instead of incremental steps