力扣Leetcode：3. 无重复字符的最长子串（C++、Python）
链接
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
题目描述
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
思路
使用递推的方法，充分利用之前的结论，避免重复计算，可以在最大程度上降低时间复杂度。
具体地，我们先以第一个位置为起点，向后查找最长的符合要求的子串[0…i]。那么接下来如何由这一结论推出以第二个位置为起点的最大子串长度呢？我们注意到，前一步遍历其实已经保证了[0…i]中不存在重复元素。我们如果把起点向右移动一个单位，其实相当于少了一个元素，因此再向后查找的时候允许与该元素重复了，相当于放开了一些限制。
代码
Python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
occ = set()
curr = 0
r = 0
for l in range(len(s)):
while r < len(s) and s[r] not in occ:
occ.add(s[r])
r += 1
curr = max(curr, r - l)
occ.remove(s[l])
return curr
C++
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int mark[128], len=s.length(), max=0, r=0;
for(int i=0; i<128; i++) {
mark[i]=0;
}
for(int l=0; l<len; l++) {
if(l>0) {
mark[int(s[l-1])]--;
}
while(r<len && !mark[int(s[r])]) {
mark[int(s[r++])]++;
}
max = (r-l)>max?(r-l):max;
}
return max;
}
};