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. ！

Portal ——>Leecode Big factory hot topic 100 Tao series problem solution

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)$, among $N$ Is the length of the string . The left pointer and the right pointer traverse the entire string once, respectively .

• Spatial complexity ：$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)$ In the character , namely $|\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(|\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;
}
};

Loneliness is very necessary , What a person does in lonely time , Determines that this person is fundamentally different from others .