[LeetCode刷題筆記] 3 - Longest Substring Without Repeating Characters

題目描述：

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:

Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

Input: s = ""
Output: 0

Constraints:

• 0 <= s.length <= 5 * 104
• s consists of English letters, digits, symbols and spaces.

一刷題解（HashSet + Two Pointers）：

這一題需要我們在一個字符串裡面找到連續出現不重複字符的最長長度。對於這類對重複項這麼敏感的題，一般都可以使用HashSet來做。因此我最開始是只使用HashSet，然後當Add失敗（出現重複項）的時候清空HashSet，比較當前長度與記錄的長度。但是這樣是不行的，這樣只是遇到重複項是就把前面的捨棄然後重新計算後面的元素，這樣是有問題的。比如 “dvdf”：預期輸出是”vdf”，長度為3，但如果是根據我最開始的做法，輸出將會是”df”，長度為2。

因此，遇到重複項時清空前面的元素是不行的，我需要遍歷數組元素（endIdx），檢查重複的同時，還需要有一個下標記錄起點（startIdx）；並在使用HashSet發現重複項時，將起點向前推移直到重複項首次出現的下標+1的位置上；然後再使用兩個指針之間的距離（endIdx - startIdx）與記錄中的最大長度進行比較。

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        if(s == string.Empty || s == null){return 0;}
        HashSet<char> charHash = new HashSet<char>();
        int maxDis = 0;
        int startIdx = 0; //起點下標
        int endIdx = 0; //終點下標
        while(endIdx < s.Length)
        {
            if(!charHash.Contains(s[endIdx]))
            {
                charHash.Add(s[endIdx]);
                endIdx++;
                maxDis = endIdx - startIdx > maxDis ? endIdx - startIdx : maxDis;
            }
            else
            {
                //移除前面的元素直到接觸到重複元素首次出現的下標+1的位置
                charHash.Remove(s[startIdx]);
                startIdx++;
            }
        }
        return maxDis;
    }
}