题目: 无重复字符的最长子串

分析

字符串问题都可以采用暴力破解法穷举所有的字符子串，然后求解问题。

暴力破解

通过两层循环来构造所有的子串，外层循环是子串的起始位置，内层循环是子串的结束位置，然后判断该子串是否有重复的字符，如果没有则是符合条件的子串，最后再比较这些符合条件子串的长度，输出最长的长度。

暴力破解法因为需要了双层循环，而且循环内的执行逻辑中是否符合无重复字符的判断也需要遍历字符，所以暴力破解的时间复杂度是O（n³）。

动态规划

如果当前位置n结尾的最长无重复子串是f(n)，那么 n+1 位置的字符如果在前面f(n)个字符中没有出现，那么f(n+1)就等于f(n)加一，否则定位到n+1位置的字符在前面字符的位置，假设该位置为m，那么n+1位置结尾的最长无重复子串就是n-m+1。

动态规划使用确定状态的变量，因为要计算截止到结尾位置的最长无重复子串，而且状态的变量使用结尾位置。

如果当前的的位置是n，那么截止在n-1的最长重复子串是f(n-1)，那么f(n)的结果取决于n位置的字符和前f(n-1)个字符中是否有重复的，如果没有重复的，f(n)=f(n-1)+1，如果有重复的，取决于重复的位置，假设重复的位置是i，那么f(n)=n-i。

边界条件是起始的第一个字母肯定是无重复的，f(1)=1。

因为要判断字母是否在之前的子串中出现过，轮询子串的每个字符是O（n）的时间复杂度，所以可以使用一个Hash表记录每个字符上一次出现的位置，可以将该比对的时间复杂度变为O（1），假如该字符位置的Hash表为char_postion。

该问题的状态转移方式如下：

$f(n)={\begin{cases}f(n-1)+1,&{\text{if }}cp[c_{n}]=null{\text{ or }}cp[c_{n}]<n-f(n-1)\\n-cp[c_{n}],&{\text{if }}cp[c_{n}]>n-f(n-1)\\1,n=1\end{cases}}$

滑动窗口

滑动窗口是值利用两个指针的滑动完成业务逻辑的方法，因为使用了两个指针，所以此类滑动窗口的方法也是双指针方法的一种应用。

两个指针以及中间的字符和在一起构成了滑动窗口。题目是求值最长无重复子串，所以要求这个窗口中不能有重复字符，该滑动窗口的宽度就是最长无重复子串。

初始阶段使用两个指针分别指向字符串的开头第一个字符以及第二个字符的位置，如果两个指针指向位置的字符不等，则右侧指针向右移动，右指针移动的过程，右指针指向的字符和左侧指针构成的滑动窗口中的字符一旦出现重复，则将左指针指向重复的字符位置加一的位置，之后继续移动右指针。在滑动窗口移动的过程中出现的最大宽度就是最长无重复子串。