#3. Longest Substring Without Repeating Characters

題目描述

給你一個字串s，找到最長的沒有重複字元的子字串的長度。

限制條件

1. 0 <= s.length <= 5 * 10⁴
2. 字串包含了字母、數字、符號與空白。

解題思路

Hashtable & Counting

這一題有兩個目標要達成。

1. 數字元。
2. 計算不重複字元的長度。

數字元就是每當處理一個新的字元，就增加長度。 計算不重複字元的長度只要在每處理一個新字元的時候，確認它是否重複，如果重複就以現在的位置減去重複出現的位置。 要注意的是重複出現字元會出現以下兩種狀況。

1. "abca" 最長長度為3。
2. "abba" 最長長度為2。

第1種狀況很好理解，用現在位置減去舊的字元出現的位置，就會得到長度。
而第2種狀況長度應該要是2，但是若是用新的a的位置減去舊的a的位置，就會得到3這個錯誤的答案。

因此要先確認舊的位置是否比現在長度的起點還要後面，才能去做相減的動作。

public class Solution {
    public int LengthOfLongestSubstring(string s) {
        if(s.Length==0) return 0;
        var ht = new Hashtable();        
        int maxLen = 0;
        int len = 0;
        for(int i=0;i<s.Length;i++){            
            len++;
            if(ht.Contains(s[i])){                
                if((int)ht[s[i]]>i-len) len = i-(int)ht[s[i]];
                ht[s[i]] = i;
            }else{                
                ht.Add(s[i],i);
            }
            maxLen = Math.Max(maxLen,len);
        }
        return maxLen;
    }
}

複雜度分析：

• 時間複雜度：O(n)。
• 空間複雜度：O(n)。

學習重點

• Hash Table
• String