[LeetCode] Longest Substring Without Repeating Characters

題目：Longest Substring Without Repeating Characters
難度：Medium

技巧在於使用 Sliding Window 去解，左右指標會一直移動，直到遍歷整個字串，即左右指標重疊。

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        if (s.Length == 0)
        {
            return 0;
        }

        // dict 的 key 為字母， value 為右邊的指標位置
        IDictionary<char, int> dict = new Dictionary<char, int>();
        int left = 0;
        int right = 0;
        int maxLength = 0;

        while (left < s.Length && right < s.Length)
        {
            char c = s[right];

            // 如果該字母存在於字典中，則移動左邊的指標
            // 因為要開一個新的 Window，所以左邊指標要移至【已存在的 c 的位置 +1】
            if (dict.ContainsKey(c))
            {
                left = Math.Max(dict[c] + 1, left);
            }
            
            // 如果該字母存在於字典中，則會更新成右邊指標的位置
            // 如果該字母不存在於字典中，則會新增
            dict[c] = right;

            // 比較【左右指標的位置差】與【前一次的最大長度】，何者比較大
            maxLength = Math.Max(maxLength, right - left + 1);

            right += 1;
        }

        return maxLength;
    }
}

參考

演算法筆記系列 — Two Pointer 與 Sliding Window
YouTube: Longest Substring Without Repeating Characters