一、題目介紹
今天要練習的是LeetCode 3：Longest Substring Without Repeating Characters

題目要求給定一個字串 s，找出其中最長的不包含重複字元的子字串，並回傳它的長度

例如：s = "abcabcbb"
其中最長的不重複子字串是："abc"
長度為3
所以答案是3

二、什麼是Substring？
這裡的Substring（子字串）指的是字串中連續的一段內容

例如：s = "abcde"
以下都是Substring：
"abc"
"bcd"
"cde"
"abcd"

但"ace"就不是Substring，因為a、c、e並不是連續的

三、解題想法：Sliding Window
這題如果直接把所有可能的子字串都列出來，再一個一個檢查有沒有重複，會需要很多時間
因此我們使用：Sliding Window（滑動視窗）

可以把它想像成字串上有一個會左右移動的框框：

其中：

• L = Left，左邊界
• R = Right，右邊界

我們讓R不斷向右移動，把新的字元加入視窗

• 如果沒有重複：視窗繼續擴大
• 如果發現重複：
  • 移動 L
  • 縮小視窗

直到視窗重新變成「沒有重複字元」

四、為什麼Sliding Window很有效率？
如果每次遇到重複都重新從頭檢查，會浪費很多時間
Sliding Window的概念是已經確認過的部分不用重新確認
左右指標都只會向右移動，不會一直來回跑

因此整個字串最多被

• 左指標掃一次
• 右指標掃一次

所以可以做到：O(n)
這比暴力法有效率很多

五、Java實作

六、Python實作

七、特殊情況
空字串：s = ""
沒有任何字元，因此0

所有字元都不同：s = "abcdef"
整個字串都沒有重複："abcdef"
答案6

八、Java與Python比較

九、時間與空間複雜度
假設字串長度為n

時間複雜度
right會從左到右走過一次，而left也只會向右移動
因此：O(n)

空間複雜度
window最多存放目前視窗中的不同字元
如果字元種類數量為m：O(m)
如果考慮一般ASCII字元，也可以視為：O(1)
因為字元種類數量有限

十、實作結果
Leetcode測試結果：Accepted

十一、今日學習心得
今天學習的Longest Substring Without Repeating Characters讓我第一次比較完整地理解 Sliding Window（滑動視窗）的概念。剛開始看到這題時，可能會想到把所有子字串找出來，再逐一確認有沒有重複字元，但這種方法在字串很長時會需要比較多的運算。

使用Sliding Window後，就可以讓兩個指標left和right控制目前正在檢查的範圍。right負責不斷向右擴大視窗，而當遇到重複字元時，就移動left，把重複的部分移出視窗。

我覺得這題最重要的是理解為什麼left不需要回到最前面重新開始。因為之前已經檢查過的內容可以直接保留，只需要縮小目前的範圍，就能繼續尋找下一個可能的最長子字串。

這次也讓我發現，雖然程式中有while迴圈，但整體時間複雜度仍然可以做到O(n)。原因是left和right都只會向右移動，每個字元不會被無限次重複處理。

透過Java的HashSet和Python的set實作後，我對Sliding Window的基本流程有更清楚的理解。之後如果遇到「連續區間、最長／最短、不能重複、符合某個條件」這類題目，就可以開始思考是不是能使用Sliding Window來解決。