MEDIUM

Longest Substring Without Repeating Characters

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

Example

Input:

s = "abcabcbb"

Output:

Explanation:
The answer is "abc", with the length of 3.

Constraints

0 ≤ s.length ≤ 5 × 10⁴
s consists of English letters, digits, symbols, and spaces.

Approach: Sliding Window with Hash Map

Time Complexity: O(n), where n is the length of the string. Each character is visited at most twice by the sliding window.
Space Complexity: O(m), where m is the size of the character set (e.g., 26 for lowercase English letters, 128 for ASCII). The hash map stores at most m characters.

C++

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        unordered_map<int, int> m; // count character frequency
        for (int i = 0, j = 0; j < s.size(); j++) {
            m[s[j]]++;
            while(m[s[j]] > 1)
                m[s[i++]]--;  // increment i until the current character count frequency is 1
            ans = max(ans, j - i + 1);
        }
        return ans;
    }
};