算法1

(动态规划) $O(n)$

这是一道动态规划的题目

1. f(i) = f(i-1)+1;
2. 先设置一个有26个桶的数组，每个桶里初始值是-1
3. 第一种情况
4. 遍历字符串，如果桶中的值<0，说明没出现过，cur++
5. 然后将这个桶中的数值改成当前出现的位置，即 pos[(s.charAt(i)-‘a’)] = i;
6. 第二种情况
7. 当当前位置减去桶中的位置>cur，说明虽然重复，但是是在最长不重复的字符串之外，不影响，所以cur++
8. 然后将这个桶中的数值改成当前出现的位置，即 pos[(s.charAt(i)-‘a’)] = i;
9. 然后当前位置重复了，先更新最大值，然后更新cur，cur就等于，当前位置减去当前字符上一次出现的位置。
10. 最后，更新最长长度即可

Java 代码

class Solution {
    public int longestSubstringWithoutDuplication(String s) {
        if(s==null||s.length()==0)
            return 0;
        int max = 0;
        int cur = 0;
        int[] pos = new int[26];
        for(int i =0;i<pos.length;i++){
            pos[i] = -1;
        }


        for(int i = 0;i<s.length();i++){
            int pre = pos[(s.charAt(i)-'a')];
            if(pre<0||(i-pre)>cur){
                cur++;
            }
            else{
                if(cur>max){
                    max = cur;
                }
                cur = i-pre;
            }
            pos[(s.charAt(i)-'a')] = i;
        }
        if(cur > max)
            max=cur;

        return max;
    }
}