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

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

解法1

思路：使用双层循环，外层循环取字符串s的每个位置，内层循环取外层循环的值至字符串末尾。在内层循环中创建一个范围为0-255的boolean数组用来判断字符是否重复出现，这比HashMap更加轻量。最后，使用一个名为maxLen的变量存放最终结果，我们在内层循环更新这个变量。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int maxLen = 0;

        for(int i=0;i < s.length();i++) {
            boolean[] bitset = new boolean[255];
            int len = 0;

            for(int j=i;j < s.length();j++) {
                if(bitset[s.charAt(j)])
                    break;
                bitset[s.charAt(j)] = true;
                len++;
            }
            maxLen = Math.max(maxLen, len);
        }

        return maxLen;
    }
}

解法2

解法一采用了双重循环，时间复杂度是O(n^2)的，我们可以使用滑动窗口方法，维护一个[i, j)，0<=i<j<=|s|的窗口，确保窗口内的字串不含重复字符。窗口的前沿是j，后沿是i。前沿滑动，直到加入到窗口内的字符出现重复。此时，我们滑动窗口后沿，直到窗口内不含重复字符。我们在窗口前沿滑动时，计算maxLen = max(maxLen, i – j). 因为是左闭右开区间，直接用i-j就是窗口的大小。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s == null || s.length() == 0)
            return 0;
        int maxLen = 0;
        boolean[] bitset = new boolean[255];
        int i = 0, j = 0; // i,j是滑动窗口的起点与终点，我们需要确保[i, j)内不存在重复字符

        while (i < s.length() && j < s.length()) {
            // 若窗口不包含字符s[j]，就将其加入bitset
            if(!bitset[s.charAt(j)]){
                bitset[s.charAt(j++)] = true;
                maxLen = Math.max(maxLen, j - i);
            }else{
                // 遇到重复字符，i开始滑动，并且从bitset中剔除，直到使窗口内不包含重复字符。
                // 此分之触发是由于字符s[j] 在 s[i, j) 中存在
                // 我们不能直接将bitset清空，然后让i = j。这样做是不对的，例如"dvdf"，当j指向第二个d时，我们将i=j，就会漏掉字母v。
                // 导致最长不重复的字串是"df"而不是"vdf"
                bitset[s.charAt(i++)] = false;
            }
        }

        return maxLen;
    }
}

参考：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/