题解 | JZ48 最长不含重复字符的子字符串
这道题虽然放在动态规划里，但是其实是一道经典的尺取法（双指针）的题目。
我们把两个指针都放在最左端，让R指针先移动。
当R指针发现，移动到这个元素发现有重复元素了，那么我们需要移动L指针。
为什么？
因为我们始终维护的是这一段区间，也就是说当发现有重复值了，这一段区间是没法使用的，那么只要包括了这段区间的答案也肯定是错误的。这样我们就需要移动左边的指针，直到保证满足约束条件，才能保证以R指针为右端点的区间，是满足条件的。
这样的遍历是找到了所有满足条件的区间，所以在这里面统计最大值即可。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param s string字符串
* @return int整型
*/
// int mp[27];
map<char, int> mp;
int lengthOfLongestSubstring(string s) {
// write code here
int L = -1, R = -1;
int ans = 0;
mp.clear();
for (int i = 0; i < s.size(); ++i) {
++R;
mp[s[R]]++;
if (mp[s[R]]>1) {
while(mp[s[R]] > 1) {
++L;
mp[s[L]]--;
if (L>R) break;
}
}
ans = max(ans, R-L);
}
return ans;
}
};
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param s string字符串
# @return int整型
#
class Solution:
def lengthOfLongestSubstring(self , s: str) -> int:
# write code here
mp = {}
L = -1
R = -1
ans = 0
for i in range(len(s)):
R += 1
tmp = mp.get(s[R], 0)
mp[s[R]] = tmp + 1
while (mp[s[R]] > 1):
L += 1
mp[s[L]] -= 1
if L > R:
break
ans = max(ans, R - L)
return ans
