題目
#

leetcode 3 - Longest Substring Without Repeating Characters (題目說明請點連結)

題目簡述
#

給定一個字串 s，請你找出其中不含有重複字元的 最長子串 的長度。

範例
#

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: 最長不重複子字串是 "abc"，長度為 3。

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: 最長不重複子字串是 "b"，長度為 1。

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: 最長不重複子字串是 "wke"，長度為 3。

解題思路
#

這題要求我們找出一個字串中不含重複字符的最長子字串的長度。我們可以使用滑動窗口的方法來解決這個問題，通過兩個指針來維持一個動態的窗口，並使用一個集合來記錄當前窗口中的字符。

解法
#

Sliding Window

初始化一個集合 set 用於記錄當前窗口中的字符
使用兩個指針 left 和 right 來維持窗口，初始都指向字串的開頭
當 right 指針小於字串長度時，執行以下步驟：
- 如果字符不在集合中，將其加入集合，更新最大長度，並移動 right 指針
- 如果字符已在集合中，從集合中移除 left 指針指向的字符，並移動 left 指針
返回最大長度

步驟
#

初始化：
- 創建集合 set，初始化 left 和 right 指針
維持窗口：
- 當 right 小於字串長度時，檢查字符是否在集合中
- 更新最大長度，移動指針
返回結果：
- 返回最大長度

例子說明
#

s = "abcabcbb"

步驟	left	right	字符	set內容	maxLen	說明
初始化	0	0	-	{}	0	初始化指針和集合
第1輪	0	1	a	{a}	1	a 不在集合中，加入集合，更新 maxLen
第2輪	0	2	b	{a, b}	2	b 不在集合中，加入集合，更新 maxLen
第3輪	0	3	c	{a, b, c}	3	c 不在集合中，加入集合，更新 maxLen
第4輪	1	4	a	{b, c, a}	3	a 在集合中，移除 left 指針指向的字符，移動 left
第5輪	2	5	b	{c, a, b}	3	b 在集合中，移除 left 指針指向的字符，移動 left
第6輪	3	6	c	{a, b, c}	3	c 在集合中，移除 left 指針指向的字符，移動 left
第7輪	4	7	b	{b, c}	3	b 在集合中，移除 left 指針指向的字符，移動 left
第8輪	5	8	b	{c, b}	3	b 在集合中，移除 left 指針指向的字符，移動 left

完整程式碼
#

java

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

         // 使用滑動窗口維持不重複子字串
         while(right < s.length()){
            char c = s.charAt(right);
            if(!set.contains(c)){
                set.add(c);
                maxLen = Math.max(maxLen, right - left + 1);
                right++;
            }else{
                set.remove(s.charAt(left));
                left++;
            }
         }
        // 返回最大長度
        return maxLen;
    }
}