3 Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = "" Output: 0

Constraints:

0 <= s.length <= 5 * 104 s consists of English letters, digits, symbols and spaces.

---

可以用一个256维的 boolean 数组储存每个字符是否出现过。用两个指针表示左右边界，开始左右边界都在0，有边界不停往右移动，直到有字符出现2次，此时左边界开始往右移动，直到重复的字符消失。由于每个字符只能有一个，左边界每次越过的字符都在 boolean 数组中标记为未出现。右边界移动时记录最长的左右边界差。

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left=0;
        int right=0;
        int max=0;
        boolean[] counted=new boolean[256];
        char c;
        for(;left<s.length();++left){
            while(right<s.length() && !counted[s.charAt(right)]){
                counted[s.charAt(right)]=true;
                max=right-left+1>max?right-left+1:max;
                ++right;
            }
            counted[s.charAt(left)]=false;
        }
        return max;
    }
}