version at: 2022-04-22

/**
1. 记录出现过的字符, 不断向前扩展子串, 直遇到重复的 -> 
    1.1. 记录当前字串 
    1.2.将重复字符弹出 
    1.3. 继续扩展
2. 返回最大的记录长度
*/

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0) return 0;

        Set<Character> set = new HashSet<>();

        int i = 0, j = 0, res = 0;
        while (i < s.length() && j < s.length()) {
            if (set.contains(s.charAt(j))) res = Math.max(res, j-i);

            while (set.contains(s.charAt(j))) set.remove(s.charAt(i++));

            set.add(s.charAt(j++));
        }

        return Math.max(res, j-i);
    }
}

/*
1. 状态定义： f[i][j] 表示i~j的子串的状态存在情况
2. 状态计算：以加入的最后一个字符分割
如果加入的状态不存在： 拷贝前一个状态值，更新对应字符的状态值
如果加入的状态存在： 更新最高位的状态值，表示字符串不合法
如果状态计算后字符串合法，更新最终结果
3. 边界： f[~][~] = 0, f[i][i] = status
 */


/*
1. 双指针搜索， 如果r的下一个存在，就一直缩减l到next不存在为止
*/

/*
字符串一定注意空串这个东西的判断
*/

class Solution {
    public int lengthOfLongestSubstring(String s) { 
        if (s == null || s.length() == 0) return 0;
        // return dp(s);
        return search(s);
    }


    public int search(String s){
        Set<Character> set = new HashSet<>();
        int l = 0, r = 0;
        int n = s.length();
        int res = 1;
        set.add(s.charAt(0));
        while (l < n && r < n - 1){
            // res = Math.max(res, r-l+1); // 因为设定了基础值，所以要等搜完一次再去更新不然漏了一次
            while (set.contains(s.charAt(1+r)))  set.remove(s.charAt(l++));
            set.add(s.charAt(++r));
            res = Math.max(res, r-l+1);
        }
        return res;
        // return Math.max(res, r-l+1);
    }

    // MLE 
    public int dp (String s ){
        int n = s.length();
        boolean[][] b = new boolean[n+1][n+1];
        BitSet[][] f = new BitSet[n+1][n+1];
        for (int i = 0 ; i <= n; i++){
            for (int j = 0; j <=n ; j++){
                f[i][j] = new BitSet();
            }
        }
        int res = 1;

        for (int i = 1 ; i <= n; i++){
            for (int j = i ; j <= n ;j ++){
                int index = (int)s.charAt(j-1);
                f[i][j] = f[i][j-1];
                if (f[i][j].get(index)) b[i][j] = true;
                f[i][j].set(index);
                if (!b[i][j]) res = Math.max(res, j-i+1); 
                else break;
            }
        }
        return res;
    }
}