中等 · 滑动窗口 · 原题

题目信息

LeetCode #3 · Longest Substring Without Repeating Characters

标签：哈希表、字符串、滑动窗口

题目要求

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 `"abc"`，所以其长度为 3。注意 "bca" 和 "cab" 也是正确答案。

示例 2:

1
2
3
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 `"b"`，所以其长度为 1。

示例 3:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 `"wke"`，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，`"pwke"` 是一个子序列，不是子串。

提示：

  • 0 <= s.length <= 10^5

  • s 由英文字母、数字、符号和空格组成

代码实现

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
29
30
31
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> st;
        int ans=0;
        int l=0,r=1;
        st.insert(s[l]);
        for(int l=0;l<s.size();l++){
            for(;r<s.size();r++){
                if(st.find(s[r])!=st.end()){
                    break;
                }
                st.insert(s[r]);
            }
            if(r==s.size()){
                ans=max(ans,r-l); break;
            }
            ans=max(ans,r-l);
            for(int i=l;i<r;i++){
                if(s[i]!=s[r]){
                    st.erase(s[i]);
                }
                else{
                    st.erase(s[i]);
                    l=i;break;
                }
            }
        }
        return ans;
    }
};

返回目录