LC 3. 无重复字符的最长子串

class Solution {
    public int lengthOfLongestSubstring(String s) {
        /*
        * 思路:
        *        单调栈
        *       构建一个用一个队列存放已经遍历过的元素, 如果当前元素在队列中已经存在, 那么不停出队到队列里
        *    和当前元素相同的元素的下一个位置, 把当前元素放进去, 每次元素入队, 都更新一次最大值, 这样遍历
        *    一遍数组, 就能得到整个字符串的最大不同子串
        * */
        Deque<Character> queue = new LinkedList<>();    // 队列
        int index = 0;                                  // 下标位置
        char[] chs = s.toCharArray();                   // 字符串转化为字符数组方便操作
        int N = chs.length;
        int ans = 0;                                    // 返回的答案, 存放最长的子串长度
        while (index < N) {
            while (index < N && (queue.isEmpty() || !queue.contains(chs[index]))) {
                queue.add(chs[index++]);            // 队列为空或者当前元素不在队列里存在, 入队
                ans = Math.max(ans, queue.size());  // 更新最大值
            }
            while (index < N && !queue.isEmpty() && queue.contains(chs[index])) {va
                queue.pollFirst();                  // 当前元素在队列里存在, 队头元素不停出队, 
            }                                   // 直到与当前元素相同的元素出队后位置
            if (index < N) {
                queue.add(chs[index++]);
                ans = Math.max(ans, queue.size());
            }
        }
        return ans;
    }
}
// 单调栈写法优化
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Deque<Character> que = new LinkedList<>();
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            while (!que.isEmpty() && que.contains(s.charAt(i)))
                que.pollFirst();
            que.add(s.charAt(i));
            ans = Math.max(ans, que.size());
        }
        return ans;
    }
}

class Solution {
    /**
    思路: dp + map 
        用一张 map 表存储每个字符上一次出现的位置
    当前位置向前推的距离 和 上一次位置能向前推出的距离 + 1, 
    小的那个就是当前位置的最长无重复字符串
    
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0)
            return 0;
        char[] str = s.toCharArray();
        // map 表记录 (char)i 字符上一次出现的位置
        int[] map = new int[128];
        // -1 表示都没出现过
        for (int i = 0; i < 128; i++)
            map[i] = -1;
        // dp[i] 表示以 i 位置字符结尾的最长无重复子串
        int[] dp = new int[str.length];
        // 初始化操作
        int ans = 1;
        map[str[0]] = 0;
        dp[0] = 1;
        // 从 1 位置开始
        for (int i = 1; i < str.length; i++) {
            // 当前位置和上一个相同字符的距离
            int cur = i - map[str[i]];
            // i-1 位置字符结尾能推出的最长无重复子串是 dp[i-1],
            dp[i] = Math.min(dp[i - 1] + 1, cur);
            ans = Math.max(ans, dp[i]);
            map[str[i]] = i;
        }
        return ans;
    }
}

// 空间压缩版本
class Solution {
    /**
    思路: dp + map 
        用一张 map 表存储每个字符上一次出现的位置
    当前位置向前推的距离 和 上一次位置能向前推出的距离 + 1, 
    小的那个就是当前位置的最长无重复字符串
    
     */
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0)
            return 0;
        char[] str = s.toCharArray();
        // map 表记录 (char)i 字符上一次出现的位置
        int[] map = new int[128];
        // -1 表示都没出现过
        for (int i = 0; i < 128; i++)
            map[i] = -1;
        // 初始化操作
        int ans = 1;
        map[str[0]] = 0;
        int pre = 1;
        // 从 1 位置开始
        for (int i = 1; i < str.length; i++) {
            // 当前位置和上一个相同字符的距离
            int cur = i - map[str[i]];
            // i-1 位置字符结尾能推出的最长无重复子串是 dp[i-1],
            pre = cur = Math.min(pre + 1, cur);
            ans = Math.max(ans, cur);
            map[str[i]] = i;
        }
        return ans;
    }
}