Longest Substring Without Repeating Characters

Problem Statement

Given a string s, find the length of the longest substring without repeating characters.

Input/Output Specifications

• Input: A string s where 0 <= s.length <= 5 * 10^4
• Output: An integer representing the length of the longest substring without repeating characters

Constraints

• s consists of English letters, digits, symbols and spaces
• 0 <= s.length <= 5 * 10^4

Examples

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Solution Approaches

Approach 1: Sliding Window with Hash Set (Optimal)

Algorithm Explanation: Use a sliding window technique with a hash set to track characters in the current window. Expand the window by moving the right pointer, and shrink it by moving the left pointer when a duplicate is found.

1. Use two pointers: left and right
2. Use a hash set to track characters in current window
3. Expand window by moving right pointer
4. When duplicate found, shrink window by moving left pointer
5. Keep track of maximum window size

Implementation:

Python:

def lengthOfLongestSubstring(s):
    """
    Find longest substring without repeating characters using sliding window
    Time: O(n)
    Space: O(min(m, n)) where m is the character set size
    """
    if not s:
        return 0
    
    char_set = set()
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        # Shrink window until no duplicates
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        
        # Add current character and expand window
        char_set.add(s[right])
        max_length = max(max_length, right - left + 1)
    
    return max_length

Java:

class Solution {
    /**
     * Find longest substring without repeating characters using sliding window
     * Time: O(n)
     * Space: O(min(m, n)) where m is the character set size
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        Set<Character> charSet = new HashSet<>();
        int left = 0;
        int maxLength = 0;
        
        for (int right = 0; right < s.length(); right++) {
            // Shrink window until no duplicates
            while (charSet.contains(s.charAt(right))) {
                charSet.remove(s.charAt(left));
                left++;
            }
            
            // Add current character and expand window
            charSet.add(s.charAt(right));
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

Go:

// lengthOfLongestSubstring - Find longest substring without repeating characters using sliding window
// Time: O(n)
// Space: O(min(m, n)) where m is the character set size
func lengthOfLongestSubstring(s string) int {
    if len(s) == 0 {
        return 0
    }
    
    charSet := make(map[rune]bool)
    left := 0
    maxLength := 0
    
    for right := 0; right < len(s); right++ {
        // Shrink window until no duplicates
        for charSet[rune(s[right])] {
            delete(charSet, rune(s[left]))
            left++
        }
        
        // Add current character and expand window
        charSet[rune(s[right])] = true
        maxLength = max(maxLength, right-left+1)
    }
    
    return maxLength
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

JavaScript:

/**
 * Find longest substring without repeating characters using sliding window
 * Time: O(n)
 * Space: O(min(m, n)) where m is the character set size
 */
function lengthOfLongestSubstring(s) {
    if (!s || s.length === 0) {
        return 0;
    }
    
    const charSet = new Set();
    let left = 0;
    let maxLength = 0;
    
    for (let right = 0; right < s.length; right++) {
        // Shrink window until no duplicates
        while (charSet.has(s[right])) {
            charSet.delete(s[left]);
            left++;
        }
        
        // Add current character and expand window
        charSet.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

C#:

public class Solution {
    /// <summary>
    /// Find longest substring without repeating characters using sliding window
    /// Time: O(n)
    /// Space: O(min(m, n)) where m is the character set size
    /// </summary>
    public int LengthOfLongestSubstring(string s) {
        if (string.IsNullOrEmpty(s)) {
            return 0;
        }
        
        HashSet<char> charSet = new HashSet<char>();
        int left = 0;
        int maxLength = 0;
        
        for (int right = 0; right < s.Length; right++) {
            // Shrink window until no duplicates
            while (charSet.Contains(s[right])) {
                charSet.Remove(s[left]);
                left++;
            }
            
            // Add current character and expand window
            charSet.Add(s[right]);
            maxLength = Math.Max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

Complexity Analysis:

• Time Complexity: O(n) - Each character is visited at most twice
• Space Complexity: O(min(m, n)) - Where m is the character set size

Trade-offs:

• Optimal time complexity
• Efficient sliding window approach
• Works for any character set
• Most commonly used solution

Approach 2: Sliding Window with Hash Map (Optimized)

Algorithm Explanation: Use a hash map to store the last occurrence of each character. This allows us to jump the left pointer directly to the position after the last occurrence of the duplicate character.

Implementation:

Python:

def lengthOfLongestSubstringOptimized(s):
    """
    Find longest substring without repeating characters using optimized sliding window
    Time: O(n)
    Space: O(min(m, n)) where m is the character set size
    """
    if not s:
        return 0
    
    char_map = {}
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        if s[right] in char_map and char_map[s[right]] >= left:
            # Jump left pointer to position after last occurrence
            left = char_map[s[right]] + 1
        
        char_map[s[right]] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

Java:

class Solution {
    /**
     * Find longest substring without repeating characters using optimized sliding window
     * Time: O(n)
     * Space: O(min(m, n)) where m is the character set size
     */
    public int lengthOfLongestSubstringOptimized(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        
        Map<Character, Integer> charMap = new HashMap<>();
        int left = 0;
        int maxLength = 0;
        
        for (int right = 0; right < s.length(); right++) {
            if (charMap.containsKey(s.charAt(right)) && charMap.get(s.charAt(right)) >= left) {
                // Jump left pointer to position after last occurrence
                left = charMap.get(s.charAt(right)) + 1;
            }
            
            charMap.put(s.charAt(right), right);
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

Go:

// lengthOfLongestSubstringOptimized - Find longest substring using optimized sliding window
// Time: O(n)
// Space: O(min(m, n)) where m is the character set size
func lengthOfLongestSubstringOptimized(s string) int {
    if len(s) == 0 {
        return 0
    }
    
    charMap := make(map[rune]int)
    left := 0
    maxLength := 0
    
    for right := 0; right < len(s); right++ {
        char := rune(s[right])
        if lastPos, exists := charMap[char]; exists && lastPos >= left {
            // Jump left pointer to position after last occurrence
            left = lastPos + 1
        }
        
        charMap[char] = right
        maxLength = max(maxLength, right-left+1)
    }
    
    return maxLength
}

JavaScript:

/**
 * Find longest substring without repeating characters using optimized sliding window
 * Time: O(n)
 * Space: O(min(m, n)) where m is the character set size
 */
function lengthOfLongestSubstringOptimized(s) {
    if (!s || s.length === 0) {
        return 0;
    }
    
    const charMap = new Map();
    let left = 0;
    let maxLength = 0;
    
    for (let right = 0; right < s.length; right++) {
        if (charMap.has(s[right]) && charMap.get(s[right]) >= left) {
            // Jump left pointer to position after last occurrence
            left = charMap.get(s[right]) + 1;
        }
        
        charMap.set(s[right], right);
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
}

C#:

public class Solution {
    /// <summary>
    /// Find longest substring without repeating characters using optimized sliding window
    /// Time: O(n)
    /// Space: O(min(m, n)) where m is the character set size
    /// </summary>
    public int LengthOfLongestSubstringOptimized(string s) {
        if (string.IsNullOrEmpty(s)) {
            return 0;
        }
        
        Dictionary<char, int> charMap = new Dictionary<char, int>();
        int left = 0;
        int maxLength = 0;
        
        for (int right = 0; right < s.Length; right++) {
            if (charMap.ContainsKey(s[right]) && charMap[s[right]] >= left) {
                // Jump left pointer to position after last occurrence
                left = charMap[s[right]] + 1;
            }
            
            charMap[s[right]] = right;
            maxLength = Math.Max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

Complexity Analysis:

• Time Complexity: O(n) - Each character visited exactly once
• Space Complexity: O(min(m, n)) - Hash map stores character positions

Trade-offs:

• More efficient than hash set approach
• Avoids unnecessary character removals
• Slightly more complex logic
• Better performance for strings with many duplicates

Approach 3: Brute Force (Not Optimal)

Algorithm Explanation: Check all possible substrings and find the longest one without repeating characters.

Implementation:

Python:

def lengthOfLongestSubstringBruteForce(s):
    """
    Find longest substring without repeating characters using brute force
    Time: O(n^3)
    Space: O(min(m, n))
    """
    if not s:
        return 0
    
    max_length = 0
    
    for i in range(len(s)):
        for j in range(i, len(s)):
            substring = s[i:j+1]
            if len(set(substring)) == len(substring):
                max_length = max(max_length, len(substring))
    
    return max_length

Complexity Analysis:

• Time Complexity: O(n³) - Three nested loops
• Space Complexity: O(min(m, n)) - For set creation

Trade-offs:

• Simple to understand
• Very inefficient
• Not suitable for large inputs
• Good for understanding the problem

Key Insights

• Sliding Window Pattern: This is a classic sliding window problem
• Character Tracking: Use hash set or hash map to track characters
• Window Expansion: Always expand the window by moving right pointer
• Window Contraction: Contract when duplicates are found
• Optimization: Jump left pointer directly to avoid unnecessary iterations

Edge Cases

1. Empty String: "" → Returns 0
2. Single Character: "a" → Returns 1
3. All Same Characters: "aaaa" → Returns 1
4. No Repeats: "abcdef" → Returns 6
5. Repeats at End: "abcabc" → Returns 3
6. Repeats at Beginning: "aabcdef" → Returns 6

How Solutions Handle Edge Cases:

• Empty string check handles null/empty inputs
• Single character case works naturally
• All same characters handled by sliding window
• No repeats case maximizes window size
• Repeats handled by window contraction

Test Cases

def test_lengthOfLongestSubstring():
    # Basic cases
    assert lengthOfLongestSubstring("abcabcbb") == 3
    assert lengthOfLongestSubstring("bbbbb") == 1
    assert lengthOfLongestSubstring("pwwkew") == 3
    
    # Edge cases
    assert lengthOfLongestSubstring("") == 0
    assert lengthOfLongestSubstring("a") == 1
    assert lengthOfLongestSubstring("aaaa") == 1
    assert lengthOfLongestSubstring("abcdef") == 6
    assert lengthOfLongestSubstring("abcabc") == 3
    assert lengthOfLongestSubstring("aabcdef") == 6
    
    # Special cases
    assert lengthOfLongestSubstring("dvdf") == 3
    assert lengthOfLongestSubstring("tmmzuxt") == 5
    
    print("All tests passed!")

test_lengthOfLongestSubstring()

Follow-up Questions

1. Longest Substring with At Most K Distinct Characters: What if you can have at most k distinct characters?
2. Longest Substring with At Most Two Distinct Characters: Special case of the above
3. Minimum Window Substring: Find the minimum window that contains all characters of another string
4. Longest Substring with At Most K Repeating Characters: What if each character can repeat at most k times?
5. Longest Substring with Unique Characters: Find the longest substring where all characters are unique

Common Mistakes

1. Not Handling Empty String: Forgetting to check for empty input
   • Problem: Runtime errors or incorrect results
   • Solution: Always check for empty/null input first
2. Wrong Window Shrinking: Not properly handling duplicate characters
   • Problem: Incorrect window size calculation
   • Solution: Ensure left pointer moves past duplicate
3. Off-by-One Errors: Incorrect window size calculation
   • Problem: Wrong length calculation
   • Solution: Use right - left + 1 for window size
4. Not Updating Max Length: Forgetting to update maximum length
   • Problem: Incorrect final result
   • Solution: Update max length in each iteration

Interview Tips

1. Start with Brute Force: Begin with the obvious solution, then optimize
2. Explain Sliding Window: Draw the window movement to show understanding
3. Discuss Trade-offs: Compare different approaches and their complexities
4. Handle Edge Cases: Always mention empty strings and single characters
5. Optimize Further: Show the hash map optimization for better performance

Concept Explanations

Sliding Window Technique: This problem demonstrates the classic sliding window pattern where we maintain a window of valid elements and slide it across the input.

Hash Set vs Hash Map: Shows when to use a set for membership testing vs a map for storing additional information (positions).

Two Pointer Technique: Advanced application of two pointers where both pointers move in the same direction but at different speeds.

Substring vs Subsequence: Important distinction - substrings are contiguous, subsequences are not necessarily contiguous.