# Leecode03. Longest substring without repeated characters -- leecode100 question series

## I'm Xiao Zhang , Determined to use the most concise code to do the most efficient expression

The following is my personal solution , Each problem includes all solutions as much as possible , And achieve the optimal solution , Welcome to collect ！ Leaving a message. ！

### Problem description

Given a string s , Please find out that there are no duplicate characters in it Longest substrings The length of .

Example 1:
Input : s = “abcabcbb”
Output : 3
explain : Because the longest substring without repeating characters is “abc”, So its length is 3.

Example 2:
Input : s = “bbbbb”
Output : 1
explain : Because the longest substring without repeating characters is “b”, So its length is 1.

Example 3:
Input : s = “pwwkew”
Output : 3
explain : Because the longest substring without repeating characters is “wke”, So its length is 3.
Please note that , Your answer must be Substring The length of ,“pwke” Is a subsequence , Not substring .

Example 4:
Input : s = “”
Output : 0

Tips ：
0 <= s.length <= 5 * 104
s By the English letters 、 Numbers 、 Symbols and spaces

### solution

• hash Watch and judge + Sliding window queue

### Complexity analysis

• Time complexity ： O ( N ) O(N) , among N N Is the length of the string . The left pointer and the right pointer traverse the entire string once, respectively .

• Spatial complexity ： O ( ∣ Σ ∣ ) O(|\Sigma|) , among Σ \Sigma Represents the character set （ The characters that can appear in a string ）, ∣ Σ ∣ |\Sigma| Represents the size of the character set . The character set is not specified in this question , So you can default to all ASCII Code in [ 0 , 128 ) [0, 128) In the character , namely ∣ Σ ∣ = 128 |\Sigma| = 128 . We need to use hash sets to store the characters that appear , The characters are at most ∣ Σ ∣ |\Sigma| individual , So the space complexity is zero O ( ∣ Σ ∣ ) O(|\Sigma|) .

class Solution {

public:
int lengthOfLongestSubstring(string s) {

int maxLen = 0;
unordered_map<char, int>um;
queue<char>q;
for(int i = 0; i < s.length(); i++) {

q.push(s[i]);
um[s[i]]++;
if(um[s[i]] == 1) maxLen = max(q.size(), maxLen);
if(um[s[i]] > 1) {

while(um[s[i]] > 1) {

um[q.front()]--;
q.pop();
}
}
}
return maxLen;
}
int max(int a, int b) {

return a > b ? a : b;
}
};