package LeetCode;

public class LeetCode3 {

    //https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/description/
    // 
    // : O(len(s))
    // : O(len(charset))
    public int lengthOfLongestSubstring(String s) {

        int[] freq = new int[256];

        int l = 0, r = -1; //s[l...r]
        int res = 0;

        //  l == 0; r == -1 
        // l == s.size(); r == s.size()-1 
        // , freq, 
        while (l < s.length()) {
            if (r + 1 < s.length() && freq[s.charAt(r + 1)] == 0)
                freq[s.charAt(++r)]++;
            else    //r || freq[s[r+1]] == 1
                freq[s.charAt(l++)]--;

            res = Math.max(res, r - l + 1);
        }

        return res;
    }


    public int lengthOfLongestSubstring2(String s) {

        int[] freq = new int[256];

        int l = 0, r = -1; //s[l...r]
        int res = 0;

        // ,  r + 1 < s.length(), ?
        // QQ @  :)
        while( r + 1 < s.length() ){

            if( r + 1 < s.length() && freq[s.charAt(r+1)] == 0 )
                freq[s.charAt(++r)] ++;
            else    //freq[s[r+1]] == 1
                freq[s.charAt(l++)] --;

            res = Math.max(res, r-l+1);
        }

        return res;
    }
    // , 
    // : O(len(s))
    // : O(len(charset))
    public int lengthOfLongestSubstring3(String s) {

        int[] freq = new int[256];

        int l = 0, r = -1; //s[l...r]
        int res = 0;

        while(r + 1 < s.length()){

            while(r + 1 < s.length() && freq[s.charAt(r+1)] == 0)
                freq[s.charAt(++r)] ++;

            res = Math.max(res, r - l + 1);

            if(r + 1 < s.length()){
                freq[s.charAt(++r)] ++;
                assert(freq[s.charAt(r)] == 2);
                while(l