Longest Substring Without Repeating Characters Algorithm

The longest substring without repeating characters problem requires finding the maximum length of a contiguous substring that contains no duplicate characters, using efficient sliding window techniques with hash maps for optimal performance.

1. Problem Restatement

Clarifying questions to ask the interviewer:

1. What is the expected size of the input string? (e.g., up to 10^5 characters)
2. Are we allowed to modify the input string, or must we work with a copy?
3. Should we return just the length of the longest substring, or also the actual substring?
4. Can the input string contain special characters, spaces, or only alphanumeric characters?
5. What is the target time complexity for the solution? (e.g., O(n) or O(n log n) is preferred)

Restatement of the problem in my own words: Given a string, I need to find the length of the longest contiguous substring that contains no repeated characters. The challenge is to efficiently identify and track character uniqueness while scanning through the string.

Clarification of inputs, outputs, and constraints:

• Input: A string of characters (could include letters, digits, special characters)
• Output: An integer representing the length of the longest substring without repeating characters
• Constraints:
  • String can be empty (length 0)
  • String can have up to 10^5 characters (based on typical FAANG constraints)
  • Characters can be any valid ASCII or Unicode characters

Assumptions I am making:

• The string can contain any printable ASCII character or beyond (Unicode support)
• The solution should be optimized for linear time complexity
• We only need to return the length, not the actual substring itself

Data shape and hidden structure: The problem exhibits a sliding window pattern where we're looking for the maximum size of a contiguous subsequence with unique elements. The hidden structure is that we can maintain a window of characters that are all distinct, and as soon as we encounter a duplicate, we need to shrink the window from the left until that duplicate is removed.

The problem has a clear "maximum subarray" or "maximum subsequence" structure, but with the additional constraint that all elements in the subsequence must be unique. This suggests we're looking for a maximum-length contiguous substring with no character repetition, which naturally maps to a sliding window approach.

2. Pattern Recognition

Identifying the pattern

The most likely pattern is sliding window technique with hash map for character frequency tracking.

Wording that signals the pattern

• "substring" - indicates we're looking for a contiguous subsequence
• "without repeating characters" - signals we need to track uniqueness and detect duplicates
• "longest" - suggests we're optimizing for maximum length while maintaining constraints

Why this fits the pattern

This is a classic maximum sliding window problem where:

1. We maintain a window that satisfies the constraint (no repeating characters)
2. We expand the window by moving the right pointer
3. When constraint is violated (duplicate found), we shrink window from left
4. We track the maximum valid window size throughout the process

Core insight

The key insight is that we can use a sliding window approach where:

• We expand our window by moving the right pointer
• When we encounter a duplicate character, we shrink the window from the left until the duplicate is removed
• At each valid window state, we track the maximum length seen so far

This pattern is optimal because:

• We process each element at most twice (once when expanding, once when contracting)
• The constraint checking is O(1) with hash map lookups
• We never revisit elements unnecessarily

3. Approach Evolution

Interview communication script:

My first instinct is to use a brute force approach where I check every possible substring and verify if it has unique characters, but that would be O(n³) time complexity because for each starting position I'd need to check all ending positions and validate uniqueness, which is O(n²) work. Let me think about how to optimize this.

I notice that if I maintain a sliding window with two pointers, I can reduce the time complexity significantly. The key insight is that once I find a duplicate character, I don't need to check all previous substrings - I can just move my left pointer forward until the duplicate is removed from the window. This gives me an O(n) solution.

Let me think about the invariants I need to maintain:

1. The window [left, right] always contains only unique characters
2. When I encounter a duplicate character at position right, I must move left pointer until that character is no longer in the window
3. At each step, I track the maximum length of valid windows seen so far

The core optimization is using a hash map to store character positions, allowing me to jump directly to the next valid starting position rather than moving left pointer one by one.

My first approach is brute force - checking all substrings and validating uniqueness. This is O(n³) because:

• For each starting position i: O(n)
• For each ending position j: O(n)
• Validating uniqueness: O(n)

This is inefficient because we're recomputing the same character checks repeatedly.

The improved approach uses a sliding window with two pointers and a hash map to track character positions. The key optimization is that when we encounter a duplicate character, instead of advancing the left pointer one by one, we can jump directly to the position right after the last occurrence of that character.

The final approach works as follows:

1. Use two pointers (left and right) to maintain a sliding window
2. Use a HashMap to store character -> most recent index mapping
3. When we see a duplicate character at position right:
   • Move left pointer to max(left, previous_position_of_char + 1)
   • This ensures no duplicates in current window
4. At each step, update maximum window size

The key invariant that must hold throughout execution is that the window [left, right] always contains only unique characters. This ensures correctness and allows us to track the maximum valid substring length.

This approach is optimal because we visit each character at most twice (once by right pointer, once by left pointer), giving us O(n) time complexity.

4. Data Structure Choice

For this problem, I'll use a HashSet as my primary data structure to track characters in the current window.

The HashSet is ideal because:

• It provides O(1) average time complexity for both contains() and add() operations
• It naturally handles the requirement to detect duplicate characters
• It's simple to understand and maintain during the sliding window process

I'll also use two pointers (left and right) to maintain the current window bounds, which is a standard approach for sliding window problems.

The HashSet maintains the invariant that at any point in the algorithm, it contains all unique characters in the current substring from left to right.

Additional helper variables:

• maxLength to track the maximum length found so far
• left and right pointers to define the sliding window

This combination provides clean, readable code with optimal performance characteristics for this specific problem.

// HashSet to store characters in current window
Set<Character> charSet = new HashSet<>();
int left = 0;
int maxLength = 0;

5. Algorithm Walkthrough

Let me trace through the algorithm with the example input "abcabcbb":

Step 1: Initialize left = 0, maxLength = 0, and charIndexMap as empty.

Step 2: Process charAt(0) = 'a':

• 'a' not in map, so add it: charIndexMap['a'] = 0
• Window size = 1, maxLength = 1

Step 3: Process charAt(1) = 'b':

• 'b' not in map, so add it: charIndexMap['b'] = 1
• Window size = 2, maxLength = 2

Step 4: Process charAt(2) = 'c':

• 'c' not in map, so add it: charIndexMap['c'] = 2
• Window size = 3, maxLength = 3

Step 5: Process charAt(3) = 'a':

• 'a' exists in map at index 0
• Since left = 0 and charIndexMap['a'] = 0, we have 0 >= 0
• Move left pointer to charIndexMap['a'] + 1 = 1
• Update charIndexMap['a'] = 3
• Window size = 3 - 1 + 1 = 3, maxLength = 3

Step 6: Process charAt(4) = 'b':

• 'b' exists in map at index 1
• Since left = 1 and charIndexMap['b'] = 1, we have 1 >= 1
• Move left pointer to charIndexMap['b'] + 1 = 2
• Update charIndexMap['b'] = 4
• Window size = 4 - 2 + 1 = 3, maxLength = 3

Step 7: Process charAt(5) = 'c':

• 'c' exists in map at index 2
• Since left = 2 and charIndexMap['c'] = 2, we have 2 >= 2
• Move left pointer to charIndexMap['c'] + 1 = 3
• Update charIndexMap['c'] = 5
• Window size = 5 - 3 + 1 = 3, maxLength = 3

Step 8: Process remaining characters:

• Continue updating map and moving left pointer when duplicates found
• Final maxLength = 3 for substring "abc"

The algorithm correctly maintains a sliding window with no duplicate characters, updating the maximum length at each step. The key insight is that when we encounter a duplicate character, we can immediately move our left pointer to just after the previous occurrence of that character, maintaining the invariant that our window always contains unique characters.

6. Java Solution

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        // Handle edge case of empty string
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        // Use a HashSet to track characters in current window
        Set<Character> charSet = new HashSet<>();
        
        // Two pointers for sliding window
        int left = 0;
        int maxLength = 0;
        
        // Expand window with right pointer
        for (int right = 0; right < s.length(); right++) {
            char currentChar = s.charAt(right);
            
            // If we've seen this character before, shrink window from left
            while (charSet.contains(currentChar)) {
                char leftChar = s.charAt(left);
                charSet.remove(leftChar);
                left++;
            }
            
            // Add current character to set
            charSet.add(currentChar);
            
            // Update maximum length
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

This solution implements the sliding window technique with two pointers to find the longest substring without repeating characters. The approach maintains a window [left, right] that always contains unique characters, expanding the window when possible and contracting it when duplicates are found.

7. Complexity Analysis

Time Complexity: O(n)

The algorithm uses a sliding window approach with two pointers that traverse the string exactly once. Each character is visited at most twice - once by the right pointer and once by the left pointer. The hash map operations (put and get) are O(1) amortized, so the overall time complexity is linear.

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

Where m is the size of the character set (e.g., 256 for ASCII) and n is the length of the string. In the worst case, we store all unique characters in the hash map. Since we only keep track of characters within the current window, the space usage is bounded by the smaller of the character set size or the string length.

The solution is optimal because:

1. We must examine each character at least once to determine the longest substring
2. The sliding window technique achieves the theoretical lower bound for this problem
3. No algorithm can solve this in less than O(n) time since we need to process all characters

The solution is near-optimal in space as well, using only the necessary storage for tracking characters within the current window.

8. Edge Cases & Pitfalls

Empty and Minimal Inputs

• Empty string: Returns 0, handled naturally by the sliding window approach
• Single character: Returns 1, correctly identified as valid substring
• Two identical characters: Returns 1, properly identifies duplicate as invalid

Duplicate Values and Repeated States

• Multiple duplicate characters: Algorithm correctly handles overlapping duplicates by resetting window start position
• Character at both ends: When a character appears at the beginning and end of substring, window properly shrinks to exclude earlier occurrence

Boundary Conditions

• All unique characters: Maximum substring length equals string length, handled by proper window expansion
• All same characters: Window properly shrinks when duplicate found, maintaining correct max length
• Very long strings: Solution handles large inputs efficiently within O(n) time complexity

Common Implementation Mistakes

• Incorrect window boundary updates: Failing to move left pointer to the correct position when duplicate found (should move to lastSeen[char] + 1 not just lastSeen[char])
• Not updating character positions: Not updating the last seen position of characters in the hash map during iteration
• Off-by-one errors: Incorrectly including or excluding boundary characters in the window calculation
• Integer overflow: Using int instead of long for very large string indices (rare in practice but worth noting)
• HashMap key collision: While unlikely with character keys, proper hash function handling is assumed in standard Java HashMap

The most critical pitfall is ensuring that when a duplicate character is found, the left pointer advances to the position right after the previous occurrence of that character, not just to the previous occurrence's index. This ensures we maintain a valid sliding window throughout execution.

9. Alternative Approaches

There are several alternative approaches to solving the longest substring without repeating characters problem, each with different trade-offs:

1. Sliding Window with HashSet: This is essentially the same approach as our solution but using a HashSet instead of HashMap to track character positions. The key difference is that we only need to know if a character exists in current window, not its exact position. This reduces space complexity from O(min(m,n)) to O(min(m,n)) where m is the size of character set, but the time complexity remains the same.

2. Brute Force with Nested Loops: We could check every possible substring by using nested loops to generate all substrings and validate each one for uniqueness. For each starting position i, we expand to the right while tracking seen characters. This approach has O(n³) time complexity due to nested loops and substring creation, making it impractical for large inputs.

3. Dynamic Programming: We could define dp[i] as the length of longest substring ending at index i. However, this approach becomes complex because we need to track character positions and handle the case where a repeated character appears in the current window. It's not as clean as the sliding window approach and doesn't provide better complexity.

4. Two Pointers with Array: Instead of HashMap, we could use a fixed-size array of size 256 (for ASCII characters) to store character positions. This is more space-efficient than HashMap for character sets and provides O(1) lookup time, but the overall complexity remains the same.

The sliding window approach with HashMap is preferred because it's intuitive, efficient, and handles all character sets uniformly. The alternatives either have worse complexity or are more complex to implement correctly while providing no significant advantages in this specific problem context.

10. Test Cases

public class TestCases {
    public static void main(String[] args) {
        // Test case 1: Basic example
        // Input: "abcabcbb"
        // Expected: 3 ("abc")
        System.out.println(lengthOfLongestSubstring("abcabcbb") == 3);
        
        // Test case 2: All unique characters
        // Input: "abcdef"
        // Expected: 6 ("abcdef")
        System.out.println(lengthOfLongestSubstring("abcdef") == 6);
        
        // Test case 3: Empty string
        // Input: ""
        // Expected: 0
        System.out.println(lengthOfLongestSubstring("") == 0);
        
        // Test case 4: Single character
        // Input: "a"
        // Expected: 1
        System.out.println(lengthOfLongestSubstring("a") == 1);
        
        // Test case 5: All same characters
        // Input: "aaaa"
        // Expected: 1
        System.out.println(lengthOfLongestSubstring("aaaa") == 1);
        
        // Test case 6: Mixed characters with repetition
        // Input: "pwwkew"
        // Expected: 3 ("wke")
        System.out.println(lengthOfLongestSubstring("pwwkew") == 3);
        
        // Test case 7: String with spaces and special characters
        // Input: "ab ba"
        // Expected: 3 ("ab ")
        System.out.println(lengthOfLongestSubstring("ab ba") == 3);
        
        // Test case 8: Longest substring at the end
        // Input: "abcdeffff"
        // Expected: 5 ("abcde")
        System.out.println(lengthOfLongestSubstring("abcdeffff") == 5);
    }
}

The test cases cover:

• Basic functionality with overlapping characters
• Edge case of empty string
• Minimal valid input (single character)
• Boundary condition with all identical characters
• Real-world scenario with actual repeating patterns
• Special character handling (spaces, etc.)
• Cases where the maximum substring appears at string boundaries

These tests ensure the solution handles all common scenarios and edge cases properly.

11. Final Summary

The core idea is to use a sliding window technique with a hash map to track character positions, achieving an optimal O(n) time and O(min(m,n)) space solution where m is the size of the character set. This approach efficiently handles all edge cases through careful invariant maintenance and provides a clean, readable implementation that scales well for large inputs. The solution's elegance lies in its ability to transform a complex problem into a simple, maintainable algorithm that processes each character exactly once.