Longest Substring Without Repeating Characters

The longest substring without repeating characters problem is a classic sliding window algorithm that efficiently finds the maximum length substring containing no repeated characters through careful window management and hash set lookups.

1. Pattern 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 dealing with ASCII or Unicode characters?
3. Should the solution handle null or empty input gracefully?
4. Do we need to return the actual substring, or just its length?
5. What is the target time complexity for follow-up? (e.g., O(n) or better)

Restatement of the pattern: This is a classic sliding window problem where we need to find the longest contiguous substring in which all characters are unique. The key insight is that we can use a two-pointer technique to maintain a "window" of characters that satisfies the uniqueness constraint, expanding and contracting this window as we traverse the string.

Signal words and constraint shape:

• "Substring" - indicates we're looking for a contiguous sequence
• "Without repeats" or "unique characters" - signals that we need to track character occurrences and detect duplicates
• "Longest" - suggests optimization over a sliding window approach
• Input is typically a string or array of characters

Assumptions made:

1. The input string contains only printable ASCII characters (or a defined character set)
2. We can modify the input structure if needed (though we'll use a sliding window approach that doesn't require mutation)
3. We're looking for the length of the longest substring, not the substring itself (unless specified otherwise)

Scenario fit: This pattern is best suited for static input scenarios where we can process the entire dataset once. It's not well-suited for streaming data where we must continuously update our result as new elements arrive, since the optimal solution requires a complete pass through the data to determine the maximum length.

2. When to Use This Pattern

Signal words and constraint shapes in a problem statement that indicate this pattern:

• "substring" or "subarray" constraints
• "unique" or "distinct" elements required
• "maximum length" or "longest" optimization goals
• "no repeating characters" or similar constraints
• Problems asking for the "most optimal" substring under specific conditions

Why this pattern fits better than the most common alternatives: This pattern is specifically suited for problems where we need to find a contiguous subsequence with unique elements, and the optimal solution requires maintaining a sliding window of valid elements. Unlike approaches that check all substrings (O(n³)) or use nested loops (O(n²)), the sliding window technique achieves O(n) time complexity by avoiding redundant computations through careful state management.

Conditions where a variation or related pattern applies instead:

• If the problem requires tracking all unique substrings rather than just finding the longest one, a hash set-based approach might be more appropriate
• For problems involving non-contiguous subsequences (not substrings), dynamic programming or backtracking approaches would be more suitable
• When the constraint is about counting unique elements rather than finding maximum length, frequency counting approaches would apply

The core insight that makes this pattern work: The key insight is that once we encounter a duplicate character, we can immediately shrink our window from the left until the duplicate is removed, rather than starting over. This allows us to maintain a valid window of unique characters throughout the traversal, ensuring we never revisit previously processed elements unnecessarily.

The pattern works best when:

1. We're looking for contiguous substructures (strings, arrays)
2. There's a clear constraint on uniqueness or repetition
3. The optimal solution can be found by maintaining a "valid" window that expands and contracts based on constraints
4. We can efficiently move the window boundaries without losing track of valid states

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's O(n³) because for each starting position, I'd need to check all ending positions and validate uniqueness, which would require another pass through the substring. Let me think about how to optimize this.

I notice that if I use a sliding window technique with two pointers, I can maintain a valid window that never contains duplicates. As I expand the right pointer, if I encounter a duplicate character, I can shrink the window from the left until that duplicate is removed. This way, I maintain an invariant where every substring within my window has no repeating characters.

The key insight is that once I find a valid substring, I should try to extend it as far as possible while maintaining uniqueness. By using a hash map to track character positions, I can efficiently move the left pointer forward when duplicates are found, achieving O(n) time complexity.

Let me walk through this step by step:

Brute-force approach: Check all substrings and validate uniqueness. For each starting position i, check all ending positions j, and for each substring s[i:j], verify no character repeats. This requires three nested loops: O(n³) time, O(1) space (excluding output). This is not ideal because it's highly redundant - we're revalidating the same character sets multiple times.

Improved approach: Sliding window with hash map. I'll use two pointers (left and right) to maintain a window of unique characters. As I expand the right pointer, I'll keep track of character positions in a hash map. When I encounter a duplicate character that's already in my current window, I'll move the left pointer forward to exclude the previous occurrence of that character. This maintains the invariant that my window always contains unique characters.

Final approach: Two-pointer sliding window with HashMap for character tracking. I'll maintain a window [left, right] where all characters are unique. For each new character at position right:

1. If it's not in current window, expand the window
2. If it's already present, shrink window from left until that character is removed
3. Track maximum window size throughout the process

The key invariant I maintain is: at any point, the substring from left to right contains no repeated characters. This allows me to compute the maximum length in a single pass.

Important invariants that must hold:

• Window [left, right] always contains unique characters
• The window is never shrunk unnecessarily (only when duplicates are found)
• Maximum length is updated only when we find a valid longer window

4. Data Structure Choice

For the longest substring without repeats problem, I'll use a HashSet as my primary data structure.

The HashSet is ideal because:

• It provides O(1) average time complexity for both insertion and lookup operations
• It naturally handles the "no repeats" constraint by quickly detecting when a character has already been seen
• It's simple to use and understand in the context of this sliding window approach

I'll also maintain a sliding window using two pointers (left and right) to track the current substring range, which is a standard technique for this type of problem.

The HashSet will store characters currently in the sliding window, allowing me to efficiently check if adding a new character would create a duplicate.

Time and space complexity:

• Time: O(n) for the sliding window traversal, where n is the string length
• Space: O(min(m,n)) where m is the size of the character set, since we store at most the unique characters in the current window

The HashSet is more appropriate than a HashMap here because I only need to track existence of characters, not their positions or counts.

For the sliding window implementation, I'll use two integer pointers (left and right) to maintain the bounds of the current valid substring, which is a clean and efficient approach for this pattern.

// HashSet to track characters in current window
Set<Character> charSet = new HashSet<>();
// Two pointers for sliding window
int left = 0;
int right = 0;

5. Algorithm Walkthrough

Let me trace through the sliding window approach with example input "abcabcbb":

Step 1: Initialize variables

• left = 0, maxLength = 0
• charIndexMap is empty

Step 2: Process character 'a' at index 0

• charIndexMap = {'a': 0}
• Window: [0, 0], length = 1
• maxLength = max(0, 1) = 1

Step 3: Process character 'b' at index 1

• charIndexMap = {'a': 0, 'b': 1}
• Window: [0, 1], length = 2
• maxLength = max(1, 2) = 2

Step 4: Process character 'c' at index 2

• charIndexMap = {'a': 0, 'b': 1, 'c': 2}
• Window: [0, 2], length = 3
• maxLength = max(2, 3) = 3

Step 5: Process character 'a' at index 3

• Character 'a' already exists at index 0
• Update left = max(0, 0 + 1) = 1
• Remove outdated index: charIndexMap = {'b': 1, 'c': 2}
• Add new index: charIndexMap = {'b': 1, 'c': 2, 'a': 3}
• Window: [1, 3], length = 3
• maxLength = max(3, 3) = 3

Step 6: Process character 'b' at index 4

• Character 'b' already exists at index 1
• Update left = max(1, 1 + 1) = 2
• Remove outdated index: charIndexMap = {'c': 2, 'a': 3}
• Add new index: charIndexMap = {'c': 2, 'a': 3, 'b': 4}
• Window: [2, 4], length = 3
• maxLength = max(3, 3) = 3

Step 7: Process character 'c' at index 5

• Character 'c' already exists at index 2
• Update left = max(2, 2 + 1) = 3
• Remove outdated index: charIndexMap = {'a': 3, 'b': 4}
• Add new index: charIndexMap = {'a': 3, 'b': 4, 'c': 5}
• Window: [3, 5], length = 3
• maxLength = max(3, 3) = 3

Step 8: Process character 'b' at index 6

• Character 'b' already exists at index 4
• Update left = max(3, 4 + 1) = 5
• Remove outdated index: charIndexMap = {'c': 5, 'a': 3}
• Add new index: charIndexMap = {'c': 5, 'a': 3, 'b': 6}
• Window: [5, 6], length = 2
• maxLength = max(3, 2) = 3

Step 9: Process character 'b' at index 7

• Character 'b' already exists at index 6
• Update left = max(5, 6 + 1) = 7
• Remove outdated index: charIndexMap = {'a': 3, 'c': 5}
• Add new index: charIndexMap = {'a': 3, 'c': 5, 'b': 7}
• Window: [7, 7], length = 1
• maxLength = max(3, 1) = 3

Step 10: Process character 'b' at index 8

• Character 'b' already exists at index 7
• Update left = max(7, 7 + 1) = 8
• Remove outdated index: charIndexMap = {'a': 3, 'c': 5}
• Add new index: charIndexMap = {'a': 3, 'c': 5, 'b': 8}
• Window: [8, 8], length = 1
• maxLength = max(3, 1) = 3

Algorithm terminates with maxLength = 3, which is correct for substring "abc".

The key invariants maintained:

1. left always points to the start of current valid window
2. charIndexMap contains only characters in current window with their latest indices
3. Window never contains duplicate characters
4. maxLength is always the maximum valid window size seen so far

6. Java Solution

public class LongestSubstringWithoutRepeats {
    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 to maintain 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 character is already in window, shrink from left
            while (charSet.contains(currentChar)) {
                char leftChar = s.charAt(left);
                charSet.remove(leftChar);
                left++;
            }
            
            // Add current character to window
            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. The key insight is to maintain a valid window where all characters are unique, expanding the window by moving the right pointer and contracting it when duplicates are found. The HashSet efficiently tracks character presence in O(1) time, making the overall solution O(n) time complexity.

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, get, remove) are O(1) amortized on average, so the overall time complexity is linear.

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

Where m is the size of the character set (e.g., 26 for lowercase letters, 128 for ASCII) and n is the length of the string. The space is used by the HashMap to store at most min(m,n) characters in the current window. In the worst case where all characters are unique, we store up to n characters, but in practice it's bounded by the character set size.

Why these bounds are correct:

• The linear traversal ensures each element is processed a constant number of times
• The HashMap size is bounded by the character set size, which is typically much smaller than the input string length
• The sliding window maintains a valid substring without repeating characters, so the window size never exceeds the character set size

Optimality:

This is optimal for the problem as stated. We must examine each character at least once to determine if it creates a repeat, making O(n) the best possible time complexity. The space complexity is also optimal since we need to store at least the characters in the longest valid substring, which is bounded by the character set size.

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 invalidating the substring

Duplicate Values and Repeated States

• Multiple duplicates: Algorithm correctly handles multiple repeated characters by shrinking window from left until no duplicates exist
• Character frequency tracking: Without proper hash map handling, duplicate character detection can be missed

Boundary Conditions

• All unique characters: Window expands to full string length, correctly returning n
• All same characters: Window shrinks immediately when duplicate found, returning 1
• String with length 10^5: Solution handles maximum input size efficiently

Common Implementation Mistakes

• Incorrect window expansion: Not advancing right pointer when valid character found, leading to infinite loop
• HashMap key handling: Using character as key but not properly managing character value updates in map
• Window shrink logic: Not properly removing characters from hash map when window shrinks, causing stale data
• Off-by-one errors: Mismanaging indices when updating max length or window bounds
• Not resetting max length: Failing to properly track maximum length seen so far during iteration

The solution must carefully maintain the invariant that the hash map only contains characters in current window, and properly update character counts when sliding the window.

9. Alternative Approaches

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

Brute Force Approach: Check all possible substrings using nested loops. For each starting position, expand until a duplicate is found. Time complexity is O(n³) - O(n²) for starting positions × O(n) to check for duplicates. This approach is inefficient and not suitable for large inputs.

HashMap-based Sliding Window: Instead of using a HashSet, we can use a HashMap to store character indices. This allows us to directly jump to the next valid starting position when we encounter a duplicate, potentially reducing some iterations. However, in practice, this approach still requires O(n) time and space and doesn't significantly improve the asymptotic complexity.

Array-based Sliding Window: Since we're dealing with ASCII characters (or a fixed character set), we can use an array of size 128 to track character occurrences instead of a HashSet. This reduces lookup time from O(log n) to O(1), making it slightly more efficient in practice but maintaining the same O(n) time complexity.

Two Pointers with Character Frequency Tracking: Using two pointers (left and right) to maintain a window, we can keep track of character frequencies in the current window. When we encounter a duplicate, we shrink the window from the left until no duplicates exist. This is essentially the same as our chosen approach but with different implementation details.

The key insight that makes our chosen solution optimal is using the HashSet for O(1) lookup and maintaining a minimal window that always contains unique characters, avoiding unnecessary iterations. The alternative approaches either don't improve the time complexity or add unnecessary overhead in implementation complexity.

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("Test 1: " + lengthOfLongestSubstring("abcabcbb"));
        
        // Test case 2: All unique characters
        // Input: "abcdef"
        // Expected: 6 ("abcdef")
        System.out.println("Test 2: " + lengthOfLongestSubstring("abcdef"));
        
        // Test case 3: Empty string
        // Input: ""
        // Expected: 0
        System.out.println("Test 3: " + lengthOfLongestSubstring(""));
        
        // Test case 4: Single character
        // Input: "a"
        // Expected: 1
        System.out.println("Test 4: " + lengthOfLongestSubstring("a"));
        
        // Test case 5: All same characters
        // Input: "aaaa"
        // Expected: 1
        System.out.println("Test 5: " + lengthOfLongestSubstring("aaaa"));
        
        // Test case 6: Mixed case with repeats
        // Input: "pwwkew"
        // Expected: 3 ("wke")
        System.out.println("Test 6: " + lengthOfLongestSubstring("pwwkew"));
        
        // Test case 7: Longest at end
        // Input: "abccba"
        // Expected: 3 ("abc")
        System.out.println("Test 7: " + lengthOfLongestSubstring("abccba"));
        
        // Test case 8: Complex overlapping
        // Input: "dvdf"
        // Expected: 3 ("vdf")
        System.out.println("Test 8: " + lengthOfLongestSubstring("dvdf"));
    }
}

Sample Test Cases:

1. Basic case: "abcabcbb" → Expected output: 3 (substring "abc")
2. All unique: "abcdef" → Expected output: 6 (entire string)
3. Empty input: "" → Expected output: 0
4. Single character: "a" → Expected output: 1
5. All duplicates: "aaaa" → Expected output: 1
6. Valid substring in middle: "pwwkew" → Expected output: 3 (substring "wke")
7. Longest at end: "abccba" → Expected output: 3 (substring "abc")
8. Complex overlap: "dvdf" → Expected output: 3 (substring "vdf")

The test cases cover:

• Normal operation with repeated characters
• Edge cases (empty, single character)
• Boundary conditions (all same chars, all unique)
• Substring positioning variations
• Complex overlapping scenarios that test the sliding window logic

11. Final Summary

The core idea is to use a sliding window technique with a HashSet to track unique characters, maintaining a balance between simplicity and efficiency. This solution works by expanding the window while all characters are unique, and contracting it when duplicates are found, ensuring we always track the maximum valid substring length. The approach is optimal with O(n) time and O(min(m,n)) space complexity, where m is the size of the character set, making it efficient for large inputs while remaining easy to understand and implement correctly.