[LeetCode]3. Longest Substring Without Repeating Characters无重复字符的最长子串

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+1个元素，这样新的不重复子串就是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<Character> set=new HashSet<Character>();
        while(i<n&&j<n){
            if(!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                max=Math.max(max,j-i);
            }else{
                set.remove(s.charAt(i++));
            }
        }
        return max;
    }
}

还可以从空间角度进行优化
当我们知道该字符集比较小的时侯，我们可以用一个整数数组作为直接访问表来替换 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