题目描述

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

示例 1:

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

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

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

方法和思路解析

方法一（暴力法）：

假设有一个函数可以判断所给定的字符串中是否含有重复字符。当没有重复字符时返回true，否则返回false。此时，上面的问题就就只需要遍历所有的字符子串，判断是否是无重复字符的字符串。在此过程记录下最长符合条件的子串长度即可。代码如下：

# solution for python3
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        for i in range(0, len(s)):
            for j in range(i+1, len(s)+1):
                if self.allUnique(i, j, s):
                    max_len = max(max_len, j - i) 
        
        return max_len

    @staticmethod
    def allUnique(start, end, s):
        lis = []
        for i in range(start, end):
            if s[i] in lis:
                return False
            lis.append(s[I])
        return True

// solution for c++
class Solution {
public:
    bool allUnique(int start, int end, string s){
        vector<char> lis;
        for(int i = start; i < end; i++){
            if(find(lis.begin(), lis.end(), s[i]) != lis.end()){
                return false;
            }
            lis.push_back(s[I]);
        }

        return true;
    }

    int lengthOfLongestSubstring(string s) {
        int str_len = int(s.size());
        int max_len = 0;
        for(int i = 0; i < str_len; i++){
            for(int j = i+1; j < str_len+1; j++){
                if (allUnique(i, j, s)) max_len = max(max_len, j - i);
            }
        }

        return max_len;
    }
};

复杂度分析：

。

方法二（滑动窗口）：

第二种方法是滑动窗口。所谓窗口是一个概念抽象。它是指一个区间（这里是个左闭右开区间）。方法一在执行过程中会多次检索不含有重复字符的子串。可以通过滑动窗口的思想来减少重复工作。left表示窗口的左节点，right表示窗口的右节点。left和right之间存放着不重复的字符子串。每次我们向右检索，当下一个字符并不存在于窗口中的子串时，窗口有边界向右滑1（即right:=right+1）。如果已经存在了，则将left右滑1（即left:=left+1)，并重复上述过程。

// solution for c++
int lengthOfLongestSubstring(string s) {
    if(s.empty()) return 0;
    int maxlen=1;
    int start=0, start_temp=0;
    for(int end=1; end<s.size(); ++end){
        start=start_temp;
        // 下面循环检查新加入的元素是否存在于前面的非重复子串中
        while(start<end){
            if(s[start]==s[end]){
                // 遇到重复字符，窗口直接调整为子串中重复字符的后面位置
                start_temp=start+1;
                break;
            }
            start++;
        }
        maxlen=max(maxlen, end-start_temp+1);
    }
    return maxlen;
}

复杂度分析：
时间复杂度：为O(2n) = O(n)。（最差情况当字符串中每个字符都一样时为2n）。

方法三（滑动窗口改良）：

和上述方法相似，只是多一步记录了重复字符位置，使得发现重复字符时不用一点一点滑动窗口的左边界。方法如下：
left和right之间存放着不重复的字符子串。每次我们向右检索，当下一个字符并不存在于窗口中的子串时，窗口有边界向右滑1（即right:=right+1）。如果已经存在了，则left换成子串中重复的那个字符之后。接着重复上述过程。

# solution for python
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if s:
            max_len = 1
            left = 0
            dic = {}
            for curr in range(len(s)):
                if s[curr] in dic:
                    left = max(dic[s[curr]] + 1, left)
                    
                dic[s[curr]] = curr
                max_len = max(max_len, curr - left + 1)

            return max_len
        else:
            return 0

// solution for c++
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if (s.empty()){
            return 0;
        }else{
            int str_len = int(s.size());
            int max_len = 1;
            int left = 0;
            unordered_map<char, int> hash;
            
            for(int i = 0; i < str_len; i++){
                if (hash.find(s[i]) != hash.end()){
                    left = max(left, hash[s[i]]+1);
                }
                hash[s[i]] = i;
                max_len = max(max_len, i - left + 1);
            }

            return max_len;
        }
    }
};

复杂度分析：
时间复杂度：为O(n)。

题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。