3. Longest Substring Without Repeating Characters - Medium

前往題目

搬運以前的文章

想法

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

思路

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

Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int l = 0, r = 0;
        Set<Character> set = new HashSet();
        int res = 0;

        while (r < s.length()) {
            char c = s.charAt(r);
            
            if (set.contains(c)) {
                // Remove the front
                set.remove(s.charAt(l));
                ++l;
            } else {
                set.add(c);
                ++r;
                res = Math.max(res, set.size());
            }
        }

        return res;
    }
}

2024/01/31

• 快速寫出來大概的code，但是細節沒能完成，有一點邏輯錯誤