题目描述
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
网友评论