3. Longest Substring Without Repeating Characters

Medium

Problem Description

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

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.
Jump to Solution: Python Java C++ JavaScript C#

Python Solution

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        seen = {}
        max_length = 0
        start = 0
        
        for end, char in enumerate(s):
            if char in seen:
                start = max(start, seen[char] + 1)
            seen[char] = end
            max_length = max(max_length, end - start + 1)
            
        return max_length

Java Solution

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map map = new HashMap<>();
        int maxLength = 0;
        int start = 0;
        
        for (int end = 0; end < s.length(); end++) {
            char c = s.charAt(end);
            if (map.containsKey(c)) {
                start = Math.max(start, map.get(c) + 1);
            }
            map.put(c, end);
            maxLength = Math.max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }
}

C++ Solution

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map map;
        int maxLength = 0;
        int start = 0;
        
        for (int end = 0; end < s.length(); end++) {
            char c = s[end];
            if (map.find(c) != map.end()) {
                start = max(start, map[c] + 1);
            }
            map[c] = end;
            maxLength = max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }
};

JavaScript Solution

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    const map = new Map();
    let maxLength = 0;
    let start = 0;
    
    for (let end = 0; end < s.length; end++) {
        const char = s[end];
        if (map.has(char)) {
            start = Math.max(start, map.get(char) + 1);
        }
        map.set(char, end);
        maxLength = Math.max(maxLength, end - start + 1);
    }
    
    return maxLength;
};

C# Solution

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        Dictionary map = new Dictionary();
        int maxLength = 0;
        int start = 0;
        
        for (int end = 0; end < s.Length; end++) {
            char c = s[end];
            if (map.ContainsKey(c)) {
                start = Math.Max(start, map[c] + 1);
            }
            map[c] = end;
            maxLength = Math.Max(maxLength, end - start + 1);
        }
        
        return maxLength;
    }
}

Complexity Analysis

Solution Explanation

This solution uses the sliding window technique with a hash map:

Key points: