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.

解题思路：

审题给定的 字符串 ，不重复字符的子字符串。

考虑到额外的存储空间或者多指针。

空间用HashSet，开始一个指针，移动一个指针。如果有重复，则再从开始指针的下一位开始traverse。

 class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        if (s.length() == 0) {
            return 0;
        }
        
        Set< Integer > set = new HashSet<Integer>();
         char [] arr = s.toCharArray();
        int head = 0, p = 0;
        int res = 0;
        while (p < arr.length) {
            if (set.contains((int)arr[p])) {
                if (set.size() > res) {
                    res = set.size();
                }
                set.clear();
                head++;
                p = head;
            } else {
                set.add((int)arr[p]);
                p++;
            }
        }
        
        if (set.size() > res) {
            return set.size();
        }
        
        return res;
        
    }
}  

上面的方式运行时长不是最优。

申请一个长度为128位的数组，为什么128，是因为ascii码的长度为128，涵盖了所有基本字符。

这个数组有什么用？记录字符出现的index。

这里重点关注start的作用。

 class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        int[] chr = new int[128];
        for (int i=0; i< chr.length; i++) {
            chr[i] = -1;
        }
        int start = 0, res = 0;
        for (int i=0; i<s.length(); i++) {
            int pos = (int) s.charAt(i);
            int val = chr[pos];
            start = Math.max(start, val + 1);
            res = Math.max(res, i - start + 1);
            chr[pos] = i;
        }
        return res;
    }
}