3 无重复字符的最长子串

本文最后更新于：2021年1月14日 晚上

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

示例 1:

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

示例 2:

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

示例 3:

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

Solution

  • 滑动窗口算法

参考 滑动窗口技巧 的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# @lc code=start
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left, right = 0, 0
        window = collections.defaultdict(int)
        res = 0
        
        while right < len(s):
            c1 = s[right]
            window[c1] += 1
            right += 1
            
            while window[c1] > 1:
                c2 = s[left]
                window[c2] -= 1
                left += 1
                
            res = max(res, right-left)
        return res
# @lc code=end

cpp

  • 参考 liuyubobobo 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        int l=0, r=0;
        int freq[256] = {0}; // 建立大小包含所有字符的数组

        while(l<s.size()){
            if(r<s.size() && freq[s[r]]==0)
                freq[s[r++]] ++;
            else
                freq[s[l++]] --;
            res = max(res, r-l);
        }
        return res;
    }
};
  • l 每次可以向前跳跃, 而不仅仅是+1
  • r 每次移动，都检查是否与窗口内元素重复
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
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int res = 0;
        int l=0, r=0;
        int freq[256] = {0};

        while(r<s.size()){
            int index = isDuplicate(s, l, r);
            if(index != -1)
                l = index+1;
            res = max(res, r-l+1);
            r++;
        }
        
        return res;
    }
private:
    int isDuplicate(const string& s, int l, int r){
        for(int i=l; i<r; ++i){
            if(s[i]==s[r])
                return i;
        }
        return -1;
    }
};
algo leetcode 算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！