Longest Substring Without Repeating Characters

。題目假設

給定一個字串，找出最長的不重複子字串

。直覺

一開始想不太出來，以為要用 dp，後來看到了提示： hashmap, two pointer 就恍然大悟，

我們可以邊掃過字元，邊丟進 hashmap裡面檢查是不是重複，一遇到重複就把 pointer 換到新的位置

。分析可行性(資結、演算法、虛擬碼)

資結：hashmap

演算法：用兩個指針，一前一後，前面邊掃邊丟進map裡面，遇到有重複的，將後指針換到該重複位置

。最後解決方案

演算法：用兩個指針，一前一後，前面邊掃邊丟進map裡面，遇到有重複的，將後指針換到該重複位置的後一個，

然後要把換到的位置前面都從 map 裡刪掉

。反饋：與一開始想的不一樣的地方、需改進的想法

與直覺幾分相似，不一樣得點是一開始我沒有用兩個指針，而是一個指針往前掃而已，

一個指針遇到 dvdf 這個例子就不行了 ，因為會將指針定位到第二個 d ，v 就沒有算進去，要用兩個指針，

遇到重複時將後指針定位到重複的後一個。

我的寫法是這樣：

while (p1 <= length && p2 <= length) {
    if (!map.containsKey(s.charAt(p1))) {
        map.put(s.charAt(p1), p1); 
    } else {
        max = Math.max(max, map.size());
        int tempP2 = map.get(s.charAt(p1)) + 1;
        for(int i=p2; i<tempP2; i++)
            map.remove(s.charAt(i));
        p2 = tempP2;
        map.put(s.charAt(p1), p1);
    }
    p1++;
}

後來看到更好的方法：

HashMap<Character, Integer> map = new HashMap<>(); //char, index
int max = 0;
for (int i = 0, j = 0; i < s.length(); i++) {
    if (map.containsKey(s.charAt(i))) {
        j = Math.max(j, map.get(s.charAt(i)) + 1);
    }
    map.put(s.charAt(i), i);
    max = Math.max(max, i-j+1);
}
return max;

其中的

j = Math.max(j, map.get(s.charAt(i)) + 1);

意思就是說每當遇到重複時，我要定位到重複位置的後一個，但又不能在目前的位置之前

看一下這個例子 abba，遇到第二個 b ，我們會把 j 定位到 2，遇到第二個 a 時，我們不能把 j 往回定位到 1

(不能往回到 index = 1 也是上面 hash map 要刪掉之前元素的理由)

反饋的點是：兩根指針的使用流程、index定位在當前和之後的寫法

。複雜度

掃一遍，O(log n)