问题
传送门：https://leetcode.cn/problems/longest-substring-without-repeating-characters/
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。思路Ⅰ ：动态规划
由于之前处理过很经典的最长递增子序列问题、最长公共子序列问题等字符串问题，都是用到了动态规划思想，因此在这里不妨也使用动态规划解题。
设置数组dp，原字符串为s，则dp[i]表示以s[i]结尾的、无重复字符的最长子串长度。那么状态转移方程如何得到呢？如果已知dp[i-1]，如何计算出dp[i]？
事实上，我们知道dp[i-1]的值后，便知道子串s[i-dp[i-1]:i-1]就是以s[i-1]为结尾、无重复字符的最长子串。那么现在将s[i]考虑进来且必须以之为结尾呢？那么必然有$dp[i] \leqslant dp[i-1]+1$，因为s[i]可能与子串s[i-dp[i-1]:i-1]中的某个字符重复，具体地：
- 若
s[i]与s[k]重复，其中$i-dp[i-1]\leqslant k \leqslant i-1$，那么只能选取子串s[k+1:i]作为无重复字符的最长子串，则$dp[i]=i-k$； - 若
s[i]不与子串s[i-dp[i-1]:i-1]中的任何字符重复，那么直接加上s[i]即可，即选取子串s[i-dp[i-1]:i]作为无重复字符的最长子串，$dp[i]=dp[i-1]+1$。
边界条件
边界条件很简单，考虑dp[0]即可。令dp[0]=1，因为此时仅有一个字符，必定无重复。
状态转移方程
我们将上述分析过程中的状态转移合并起来，归结为如下状态转移方程
代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int dp[50005];
dp[0] = 1;
int i, j;
for(i=1; i<s.size(); i++) {
for(j=i-1; j>=i-dp[i-1]; j--) {
if(s[j] == s[i]) break;
}
dp[i] = i - j;
}
int ans = 0;
for(i=0; i<s.size(); i++) {
ans = max(ans, dp[i]);
}
return ans;
}
};算法分析
事实上，动态规划的时间复杂度比较大。由于设置了双层循环，时间复杂度基本上达到$\mathcal{O}(n^2)$。接下来的滑动窗口算法将时间复杂度大幅降低。
思路Ⅱ：滑动窗口
我们考虑字符串abcabcbb。如果我们能够计算出以每一个字符开头的无重复字符的最长子串长度，也可以得到答案。于是可以得到
- (abc)abcbb
- a(bca)bcbb
- ab(cab)cbb
- abc(abc)bb
- abca(bc)bb
- abcab(cb)b
- abcabc(b)b
- abcabcb(b)
当考虑到$s[i]$开头的无重复字符最长子串时，假设该子串为$s[i:r_k]$，那么其中必然有字符与$s[r_k+1]$重复，此时进而考虑$s[i+1:r_k+1]$是否有重复字符即可。因此可以用到滑动窗口来解决此题。
滑动窗口的通常做法，通常需要设置两个指针：左指针和右指针。两个指针都只能往右移动，且每次仅能移动其中一个指针。
- 固定左指针、右移右指针时，此时是扩张操作；
- 固定右指针、右移左指针时，此时是收缩操作。
因此，我们将左右指针初始化为0，然后先进行扩张操作，直到达到无重复字符的最大子串，再将左指针右移一位，进行扩展操作，如此反复直至右指针到达字符串末尾。
那么如何判断左指针、右指针夹住的滑动窗口子串满足无重复字符的最大子串呢？其实可以维护一个哈希表，只需检查哈希表中是否存在字符即可判定是否存在重复字符了。
代码
class Solution {
public:
map<char, int> cnt;
int lengthOfLongestSubstring(string s) {
int l, r;
l = r = 0;
int ans = 0;
while(l < (int)s.size() && r < (int)s.size()) {
// 计算以s[l]开头的无重复字符的最长子串长度，此时尝试右移右指针（扩张）
while(r < (int)s.size() && cnt[s[r]] == 0) {
cnt[s[r++]] = 1;
}
// s[l:r-1]无重复
ans = max(ans, r - l);
// 右移左指针，收缩
cnt[s[l++]] = 0;
}
return ans;
}
};
