3. Longest Substring Without Repeating Characters - Medium

前往題目

搬運一下之前的心得

想法

• 這題也沒寫出來，有嘗試用2 pointers和hashmap做，但失敗了
• 解法看了半小時才懂，卡在為甚麼要remove那個character，當發現有同樣的時候
• 原因是因為那整個substring都不能要了，也記錄了長度，所以會逐漸remove

思路

1. Set儲存substring
2. Sliding window
3. char沒在set裡面的話就加進去，然後看看有沒有更長
4. 在的話就remove left pointer的值(為什麼不是right pointer，因為那整個substring直到重複的那個都不要了，藉由循環會剛好把整個set不需要的都remove掉，只留下可以繼續使用的substring)

如果看不懂就直接跑一遍code，並使用pwwkew這個測資

Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0, r = 0, max = 0;

        Set<Character> set = new HashSet();

        // Until r pointer reach the end
        while (r < s.length()) {
            if (!set.contains(s.charAt(r))) {
                set.add(s.charAt(r));
                ++r;
                max = Math.max(max, set.size());
            } else {
                set.remove(s.charAt(l));
                ++l;
            }
        }
        return max;
    }
}