Longest Substring Without Repeating characters

3.Longest Substring Without Repeating Characters

String

Hash Table

Sliding Window

Two Pointers

Problem Statement:

Given a string s, find the length of the longest substring without repeating characters. A substring is a contiguous sequence of characters within the string.

Example:

Input:

s = "abcabcbb"

→

Output:

3

The answer is "abc", with length 3

Algorithm:

1. Use HashMap to store character positions
2. Maintain window start position
3. Update start when duplicate found
4. Track maximum length seen so far

Complexity:

Time: O(n) | Space: O(min(m,n)) where m is charset size

Java Solution:

public int lengthOfLongestSubstring(String s) {
    Map<Character, Integer> map = new HashMap<>();
    int start = 0, len = 0;
    
    for(int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        
        // Update window start if duplicate found after start
        if (map.containsKey(c)) {
            if (map.get(c) >= start)
                start = map.get(c) + 1;
        }
        
        // Update max length and character position
        len = Math.max(len, i - start + 1);
        map.put(c, i);
    }
    
    return len;
}

Python Solution:

def lengthOfLongestSubstring(self, s: str) -> int:
    char_map = {}
    start = max_len = 0
    
    for i, c in enumerate(s):
        # Update window start if duplicate found after start
        if c in char_map and char_map[c] >= start:
            start = char_map[c] + 1
        
        # Update max length and character position
        max_len = max(max_len, i - start + 1)
        char_map[c] = i
    
    return max_len

C++ Solution:

int lengthOfLongestSubstring(string s) {
    unordered_map<char, int> char_map;
    int start = 0, max_len = 0;
    
    for(int i = 0; i < s.length(); i++) {
        # Update window start if duplicate found after start
        if (char_map.count(s[i]) && char_map[s[i]] >= start) {
            start = char_map[s[i]] + 1;
        }
        
        # Update max length and character position
        max_len = max(max_len, i - start + 1);
        char_map[s[i]] = i;
    }
    
    return max_len;
}