不重复最长子串的长度

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

1.暴力求解(会超时) 时间复杂度达到0(n^3)

import java.util.HashSet;
import java.util.Set;

public class SolutionSubString {
    public static int lengthoflongestsubString(String s){
        int n = s.length();
        int max = 0;
        for (int i=0;i<n;i++)
            for (int j=i+1;j<=n;j++){
                if (allUnique(s,i,j))
                    max = Math.max(max,j-i);
            }
        return max;
    }
    public static boolean allUnique(String s, int start, int end){
        Set<Character> set = new HashSet<>();
        for (int i=start;i<end;i++){
            Character character = s.charAt(i);
            if (set.contains(character)) return false;
            set.add(character);
        }
        return true;
    }
}

2.滑动窗口(时间复杂度O(2n))
所以我们可以换个思路,就是把i到j当成一个块(窗口),j去慢慢地增大,知道找到相同的,然后就从左边开始i增大,这样就避免的吧找过的字符串重复找

public class SolutionSubString {
    public static int lengthoflongestsubString(String s){
        int n = s.length();
        int max = 0;
        int i = 0,j = 0;
        Set<Character> set = new HashSet<>();
        while (i<n&&j<n){
           if (!set.contains(s.charAt(j))){
               set.add(s.charAt(j++));
               max = Math.max(max,j-i);
           }else {
               set.remove(s.charAt(i++));
           }
        }
        return max;
    }
}