LeetCode Daily Question 9

Mar 14th 2022

3 月 14 日 每日一题

题目：3. Longest Substring Without Repeating Characters

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

思路

本题使用 sliding Window 的解法，设 left 和 right，用 hashmap 记录字母出现频率。向右移动 right，如果当前字母出现次数不为 0，代表该 no repeating substring 已经到终点，此时右移 left，并减一 map 中的频率，直到 counts[right]频率为 0，则新的 no repeating substring 开始。
时间复杂度为 O(n)，空间复杂度 O(1)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.length() == 0){
            return 0;
        }
        unordered_map<char, int>counts;
        int left = 0;
        int right = 1;
        int res = 1;
        counts[s[left]]++;
        while(right < s.length()){
            int temp = right - left;
            while(counts[s[right]] >= 1){
                counts[s[left]]--;
                left++;
                temp--;
            }
            while(right < s.length() && counts[s[right]] == 0){
                counts[s[right]]++;
                right++;
                temp++;
            }
            res = max(temp,res);
        }
        return res;
    }
};
, ,
  1. 3 月 14 日 每日一题
    1. 题目：3. Longest Substring Without Repeating Characters
    2. 思路
    3. 代码