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

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 ) O(N) O(N), among N 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|) O(Σ), 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) [0,128) In the character , namely ∣ Σ ∣ = 128 |\Sigma| = 128 Σ=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|) O(Σ).

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 .

Please bring the original link to reprint ,thank
Similar articles

2021-10-14

2021-10-14

2021-10-14

2021-10-14

2021-10-14

2021-10-14

2021-10-14