当前位置:网站首页>Leecode03. Longest substring without repeated characters -- leecode100 question series

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

2021-10-14 05:47:11 Old fellow iron has dried up the code.

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 .

版权声明
本文为[Old fellow iron has dried up the code.]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/10/20211002145845264o.html

随机推荐