Related Topics：[Hash Table][Two Pointers][String]
Similar Questions
[Longest Substring with At Most Two Distinct Characters]

題目：Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

思路

設置兩個指針，分別標識字符串中不重復子字符串的左部和右部。右指針不斷向后移動，并將查找過的元素存下來，同時更新長度。當右指針所指元素已查找過時，將左指針移動到重復元素的后一位。

根據(jù)存儲已查元素的不同，可以有以下三種解法：

解法1

使用set，把出現(xiàn)過的字符都放入set中，遇到set中沒有的字符就加入set中并更新結果，如果遇到重復的，則從左邊開始刪字符，直到刪到重復的字符停止。

java解法1

class Solution {
    public int lengthOfLongestSubstring(String s) {
         int l=0,left=0,right=0;        
         //滑動窗口解法1：set結構
         Set<Character> set=new HashSet<>();
         while(right<s.length()) {
             if(!set.contains(s.charAt(right))) {
                 set.add(s.charAt(right++));
                 l=l>set.size()? l:set.size();
             }else {
                 //左指針向右移動，直到移動到重復元素
                 set.remove(s.charAt(left++));
             }
         }
         return l;
    }
}

解法2

使用map,直接跳到重復的字符之后。

java解法2

        //滑動窗口解法2：map結構
        Map<Character,Integer> map=new HashMap<>();
        int l=0;
        //i為left j為right
        for(int i=0, j=0;j<s.length();j++) {
            if(map.containsKey(s.charAt(j))) {
                i=Math.max(i,map.get(s.charAt(j))+1);
            }
            l=Math.max(l,j-i+1);
            //根據(jù)map的性質，當存儲重復元素時，新的value值即索引將會覆蓋舊值
            map.put(s.charAt(j),j);
        }
        return l;

解法3

利用ASCII編碼，使用256大小數(shù)組存儲各字符索引。

java解法3

        //滑動窗口解法3：數(shù)組存儲ASCII
        int[] m=new int[256];
        int l= 0;
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < s.length(); j++) {
            i = Math.max(m[s.charAt(j)], i);
            l = Math.max(l, j - i + 1);
            m[s.charAt(j)] = j + 1;
        }
        return l;