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

Example 1:

Input: "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: "bbbbb"

Output: 1

Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"

Output: 3

Explanation: The answer is "wke", with the length of 3.

Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

题目要求一个最长的无重复的子串（子串要求连续），我们可以想到使用set来操作，set可以保证内部元素全部是无重复的，这比我们使用暴力方法去遍历判断重复要优化很多。简单来说就是遍历一次字符串，用i和j来标记子串的开始和结束。每次遇到不同的就把元素加入到set中，同时子串长度+1,遇到相同的就从当前子串的开头开始删除，一直删除到重复元素的位置，比如说从i开始的第n个元素重复了，就删除掉从i到n的所有元素，这样新的不重复子串就是string[i+n+1,j+1]，再和旧的长度比较出最大的，如此重复直到字符串末尾。

由于很像网络流量控制的滑动窗口协议，所以这种方法也叫滑动窗口

class Solution {    public int lengthOfLongestSubstring(String s) {        int n=s.length(),max=0;        int i=0,j=0;        HashSet
     
       set=new HashSet
      
       ();        while(i
       
      
     

还可以从空间角度进行优化

当我们知道该字符集比较小的时侯，我们可以用一个整数数组作为直接访问表来替换 Map。

常用的表如下所示：

int [26] 用于字母 ‘a’ - ‘z’或 ‘A’ - ‘Z’int [128] 用于ASCII码int [256] 用于扩展ASCII码

public class Solution {    public int lengthOfLongestSubstring(String s) {        int n = s.length(), ans = 0;        int[] index = new int[128]; // current index of character        // try to extend the range [i, j]        for (int j = 0, i = 0; j < n; j++) {            i = Math.max(index[s.charAt(j)], i);            ans = Math.max(ans, j - i + 1);            index[s.charAt(j)] = j + 1;        }        return ans;    }}

python的话可以使用列表自带的切片来维护一个不重复集合set

class Solution:    def lengthOfLongestSubstring(self, s):        """        :type s: str        :rtype: int        """        max_number = 0        number = 0        test = ''        for i in s:            if i not in test:                test += i                number += 1            else:                if number >= max_number:                    max_number = number                index = test.index(i)                test = test[(index+1):] + i                number = len(test)        if number > max_number:            max_number = number        return max_number