Longest Substring Without Repeating: Multiple Solutions and Complexity Analysis

Understanding the Problem: Longest Substring Without Repeating Characters

Given a string s, the task is to find the length of the longest contiguous substring that contains no duplicate characters. This is one of the most frequently encountered problems in coding interviews and competitive programming because it tests a developer's ability to move from brute-force thinking to optimized sliding window techniques.

Example scenarios:

• "abcabcbb" → Output: 3 (substring "abc")
• "bbbbb" → Output: 1 (substring "b")
• "pwwkew" → Output: 3 (substring "wke")
• "" (empty string) → Output: 0
• "a" → Output: 1

Why This Problem Matters

Beyond interview preparation, this problem models real-world scenarios such as:

• Data stream deduplication: Finding the longest unique sequence in network packets or log entries
• Text processing: Extracting unique token sequences in natural language processing
• Cache design: Managing sliding windows of unique resource identifiers
• Bioinformatics: Identifying longest unique subsequences in DNA strings where repetition matters

The problem also serves as a perfect teaching vehicle for the sliding window technique—a pattern that appears across dozens of algorithmic challenges.

Solution 1: Brute Force — Checking Every Substring

The most intuitive approach examines every possible substring and checks whether it contains all unique characters. While straightforward to implement, this solution is highly inefficient for longer inputs.

Algorithm Steps

• Generate all substrings using two nested loops (start index i, end index j)
• For each substring, verify uniqueness by scanning through its characters
• Track the maximum length among all valid substrings

Code Implementation

/**
 * Brute Force Approach O(n³)
 * @param {string} s - Input string
 * @return {number} - Length of longest substring without repeating characters
 */
function lengthOfLongestSubstringBruteForce(s) {
    let maxLength = 0;
    const n = s.length;

    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            // Check if substring s[i..j] has all unique characters
            if (allUnique(s, i, j)) {
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }
    }
    return maxLength;
}

function allUnique(s, start, end) {
    const set = new Set();
    for (let k = start; k <= end; k++) {
        if (set.has(s[k])) {
            return false;
        }
        set.add(s[k]);
    }
    return true;
}

Complexity Analysis

• Time Complexity: O(n³) — We have O(n²) substrings, and each uniqueness check costs O(n) in the worst case. For a string of length 100, this means roughly 500,000 operations.
• Space Complexity: O(min(n, m)) — The set stores at most m distinct characters where m is the character set size (e.g., 26 for lowercase English, 128 for ASCII).

Verdict: Unacceptable for production use. A string of length 10,000 would require trillions of operations.

Solution 2: Sliding Window with HashSet — O(2n)

The first major optimization uses a sliding window controlled by two pointers (left and right) along with a HashSet to track characters currently in the window. When a duplicate is detected, we shrink the window from the left until the duplicate is removed.

How It Works

• Expand the window by moving right pointer one step at a time
• If s[right] is already in the set, incrementally move left forward and remove characters from the set until the duplicate is gone
• At each step, update the maximum window size

Code Implementation (JavaScript)

/**
 * Sliding Window with HashSet — O(2n) time
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstringHashSet(s) {
    const charSet = new Set();
    let left = 0;
    let maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        const currentChar = s[right];

        // Shrink window while duplicate exists
        while (charSet.has(currentChar)) {
            charSet.delete(s[left]);
            left++;
        }

        // Now safe to add and expand
        charSet.add(currentChar);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

Step-by-Step Trace for "abcabcbb"

Initial: left=0, right=0, set={}, max=0

right=0 ('a'): set={'a'}, window="a", max=1
right=1 ('b'): set={'a','b'}, window="ab", max=2
right=2 ('c'): set={'a','b','c'}, window="abc", max=3
right=3 ('a'): duplicate 'a' detected → shrink: remove 'a', left=1
             set={'b','c'}, add 'a' → set={'b','c','a'}, window="bca", max=3
right=4 ('b'): duplicate 'b' → shrink: remove 'b', left=2
             set={'c','a'}, add 'b' → set={'c','a','b'}, window="cab", max=3
right=5 ('c'): duplicate 'c' → shrink: remove 'c', left=3
             set={'a','b'}, add 'c' → set={'a','b','c'}, window="abc", max=3
right=6 ('b'): duplicate 'b' → shrink: remove 'a' (left=4), remove 'b' (left=5)
             set={'c'}, add 'b' → set={'c','b'}, window="cb", max=3
right=7 ('b'): duplicate 'b' → shrink: remove 'c' (left=6), remove 'b' (left=7)
             set={}, add 'b' → set={'b'}, window="b", max=3

Final: maxLength = 3

Complexity Analysis

• Time Complexity: O(2n) — In the worst case, each character is visited twice (once by right, once by left). This simplifies to O(n).
• Space Complexity: O(min(n, m)) — The set stores at most the size of the character set or the string length.

Solution 3: Sliding Window with HashMap — True O(n) Single Pass

While Solution 2 requires a while loop that could iterate multiple times per step, we can achieve a strict single-pass O(n) by using a HashMap to store the most recent index of each character. When a duplicate is found, we jump the left pointer directly to max(left, map.get(char) + 1), skipping incremental shrinking.

Key Insight

Instead of deleting characters one by one from the set, we remember where each character last appeared. If we encounter a character whose last occurrence is within the current window (index >= left), we instantly move left past that occurrence. This guarantees each character is processed exactly once.

Code Implementation (JavaScript)

/**
 * Optimized Sliding Window with HashMap — True O(n)
 * @param {string} s
 * @return {number}
 */
function lengthOfLongestSubstringHashMap(s) {
    const charIndexMap = new Map(); // char → last seen index
    let maxLength = 0;
    let left = 0;

    for (let right = 0; right < s.length; right++) {
        const currentChar = s[right];

        // If character was seen AND its last occurrence is within current window
        if (charIndexMap.has(currentChar) && charIndexMap.get(currentChar) >= left) {
            // Jump left directly past the previous occurrence
            left = charIndexMap.get(currentChar) + 1;
        }

        // Update / add character's latest index
        charIndexMap.set(currentChar, right);

        // Window size: right - left + 1
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

Alternative Implementation (Python)

def length_of_longest_substring(s: str) -> int:
    char_index = {}
    max_length = 0
    left = 0
    
    for right, char in enumerate(s):
        # If char was seen and is within current window
        if char in char_index and char_index[char] >= left:
            left = char_index[char] + 1
        
        char_index[char] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

Complexity Analysis

• Time Complexity: O(n) — Each character is visited exactly once by the right pointer, and the left pointer jumps directly without intermediate steps.
• Space Complexity: O(min(n, m)) — The map stores up to m entries (size of character set).

Solution 4: Array-Based Index Mapping (For Known Character Sets)

When the character set is constrained (e.g., ASCII 128 or extended ASCII 256), we can replace the HashMap with a fixed-size integer array for even faster access and slightly less memory overhead. This is the most performant variation in languages like C, Java, or Rust where array indexing is extremely fast.

Code Implementation (Java)

public int lengthOfLongestSubstring(String s) {
    // Assuming standard ASCII (128 characters)
    int[] lastIndex = new int[128];
    
    // Initialize with -1 to indicate "not yet seen"
    Arrays.fill(lastIndex, -1);
    
    int maxLength = 0;
    int left = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s.charAt(right);
        
        // If character was seen in current window
        if (lastIndex[c] >= left) {
            left = lastIndex[c] + 1;
        }
        
        lastIndex[c] = right;
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

Code Implementation (C++)

int lengthOfLongestSubstring(string s) {
    vector lastIndex(128, -1);
    int maxLength = 0;
    int left = 0;
    
    for (int right = 0; right < s.length(); right++) {
        char c = s[right];
        
        if (lastIndex[c] >= left) {
            left = lastIndex[c] + 1;
        }
        
        lastIndex[c] = right;
        maxLength = max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

Complexity Analysis

• Time Complexity: O(n) — Same linear scan, but array access is O(1) with a smaller constant factor than hash map operations.
• Space Complexity: O(m) — Fixed array of size 128 or 256, independent of input string length. This is O(1) in the context of a bounded character set.

Comprehensive Complexity Comparison

Edge Cases and Robustness

Empty String

All implementations should return 0 for an empty string. Ensure your loop condition handles s.length === 0 gracefully.

Single Character String

A string like "a" should return 1. The sliding window must correctly handle the case where left and right start at the same position.

All Unique Characters

For "abcdef", the window expands to the entire string length without ever shrinking. The algorithm must correctly return n.

All Same Characters

For "aaaaaa", the window should never exceed size 1. The left pointer jumps to right at each step in the optimized version.

Unicode and Multi-byte Characters

In languages like JavaScript, strings are UTF-16 encoded. Characters like emoji ("😊") occupy two code units. Use Array.from(s) or iterate over code points if full Unicode support is required. The HashMap approach naturally handles this since it keys on actual characters, not bytes.

Very Long Strings

For strings of length 10⁶ or more, the O(n) solutions with minimal constant factors (array-based or HashMap) are essential. Memory usage should also be monitored—if the character set is unbounded (e.g., arbitrary Unicode), the HashMap could grow large, but it's bounded by the string length.

Best Practices and Production Considerations

• Choose the right variant for your constraints: If you know the input is ASCII (e.g., in network protocols or configuration parsers), use the fixed-array approach for maximum speed. For general Unicode text, use the HashMap version.
• Prefer readability in collaborative codebases: The HashSet + while loop version is the easiest to understand at a glance. Use it unless performance profiling indicates otherwise.
• Always clarify the character set in interviews: Asking "What characters can appear in the string?" shows engineering thoughtfulness and may let you use the simpler array solution.
• Write unit tests covering edge cases: Empty string, single char, all unique, all duplicates, mixed cases, spaces, special characters, and Unicode.
• Consider using a helper function for clarity: Encapsulate the logic in a well-named function with JSDoc/docstring comments describing the contract.

Production-Ready Example with Validation

/**
 * Finds the length of the longest substring without repeating characters.
 * 
 * @param {string} s - The input string (supports Unicode via code point iteration)
 * @returns {number} Length of the longest unique-character substring
 * @throws {TypeError} If input is not a string
 */
function lengthOfLongestSubstring(s) {
    if (typeof s !== 'string') {
        throw new TypeError('Input must be a string');
    }
    
    if (s.length === 0) return 0;
    
    const charIndex = new Map();
    let maxLength = 0;
    let left = 0;
    
    // Use for...of with Array.from for proper Unicode support
    const characters = Array.from(s);
    
    for (let right = 0; right < characters.length; right++) {
        const char = characters[right];
        
        if (charIndex.has(char) && charIndex.get(char) >= left) {
            left = charIndex.get(char) + 1;
        }
        
        charIndex.set(char, right);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

Common Pitfalls to Avoid

• Forgetting to handle the empty string: Always return 0 for s.length === 0.
• Using charIndexMap.get(char) > left instead of >=: The condition must be >= left because if the last occurrence is exactly at left, it's still inside the current window and must trigger a jump to left + 1.
• Not updating the map after jumping left: Always set charIndexMap.set(char, right) regardless of whether a jump occurred—the current occurrence is now the most recent.
• Off-by-one in window size calculation: Window size is right - left + 1, not right - left. Test with a single character to verify.
• Assuming characters are single bytes: In languages with byte-indexed strings (C, Go), multi-byte UTF-8 characters require careful handling.

Conclusion

The Longest Substring Without Repeating Characters problem is a classic example of how algorithmic optimization progresses from brute force (O(n³)) through incremental improvement (O(2n) with HashSet) to an elegant single-pass solution (O(n) with HashMap or array index mapping). The key insight—jumping the left pointer directly past a known duplicate's last occurrence—transforms what seems like a two-pointer coordination problem into a clean linear scan.

For most real-world applications, the HashMap-based sliding window offers the best balance of simplicity, performance, and Unicode compatibility. When working within constrained character sets like ASCII, the fixed-array variant squeezes out additional performance. Whichever implementation you choose, understanding the progression of solutions gives you a powerful mental model for the sliding window technique that applies broadly across substring and subarray problems.

Remember: The problem isn't just about finding the answer—it's about developing the intuition to recognize when a naive approach can be transformed into an efficient linear scan through clever state tracking.