今天來刷一題經典的字串題目：Longest Substring Without Repeating Characters。
題目就是要找一個字串中「最長的不重複子字串」長度。

題目範例

Input: "abcabcbb" → Output: 3
最長的是 "abc"，長度為 3。

Input: "bbbbb" → Output: 1
因為只有 "b"。

Input: "pwwkew" → Output: 3
這裡最長是 "wke"。

解題方向

一開始我以為要用兩層迴圈暴力解（檢查每個子字串），但這樣時間複雜度會是 O(n²)，字串長度最多可以到 5 萬，直接炸掉。

後來才想到這題可以用 滑動視窗 (Sliding Window)：

準備一個 HashSet 記錄目前子字串的字元。

右指針往右走，每次檢查新的字元。

如果遇到重複，就把 左指針往右移，把重複的字元踢掉。

隨時更新最大長度。

這樣時間複雜度就是 O(n)，很剛好！

Java 程式碼
import java.util.*;

class Solution {
public int lengthOfLongestSubstring(String s) {
Set set = new HashSet<>();
int left = 0, right = 0, maxLen = 0;

    while (right < s.length()) {
        char c = s.charAt(right);
        while (set.contains(c)) {
            set.remove(s.charAt(left));
            left++;
        }
        set.add(c);
        maxLen = Math.max(maxLen, right - left + 1);
        right++;
    }
    return maxLen;
}

}

public class Main {
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.lengthOfLongestSubstring("abcabcbb")); // 3
System.out.println(sol.lengthOfLongestSubstring("bbbbb")); // 1
System.out.println(sol.lengthOfLongestSubstring("pwwkew")); // 3
}
}

小心得

這題讓我體驗到「滑動視窗」的威力，本來覺得子字串的問題都會很麻煩，但只要用兩個指針去維護一個區間，就可以高效率解決。