[LeetCode] Longest Substring Without Repeating Characters

題目:

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

想法 :

1. Brute-force:設字串長度為 n, 考慮所有數對 (i, k), 0 <= i < n, 0 < k <= n - i，檢查以 s[i] 起頭，長度為 k 的子字串是否滿足條件，並記下長度，再回傳其最大值。直接了當，時間複雜度為 O(n^2)，於目前測資來看，必定超時。
2. DP: 使用大小為 256 的整數陣列 buffer 來記錄各字母出現的位置。同樣考慮數對 (i, k)，在掃過字串時，更新 (i, k) 。假設目前掃到的足標為 j ，此時有兩種情形
   • s[j] 未在 (i, k) 代表的子字串出現過，即 buffer[s[j]] < i，++k 後繼續下一個文字。
   • s[j] 已在 (i, k) 代表的子字串出現過，即 buffer[s[j]] >= i，記下當下長度 k ，更新 i 為 buffer[s[j]] + 1(因 s[buffer[j]] 與 s[j] 相同，起點為 buffer[j] 之前，長度為 k 的子字串必包含相同文字)，更新 buffer[s[j]] = j。 k 之最大值即為所求。時間複雜度為 O(n)，空間複雜度為 O(m)，m 為字串中可能出現的字母種類數。
   
   code:
   

   class Solution {
   public:
       int lengthOfLongestSubstring(string s) {
           if (s.size() == 0) {
               return 0;
           }
       
           int usedChars[256] = {0};
       
           for (size_t i = 0; i < 256; ++i) {
               usedChars[i] = -1;
           }
       
           int ret = 0;
           int length = 0;
           int start = 0;
       
           for (int i = 0; i < s.size(); ++i) {
               ++length;
       
               if (usedChars[s[i]] >= 0 && usedChars[s[i]] >= start) {
                   start = usedChars[s[i]] + 1;
                   length = i - usedChars[s[i]];
               }
               usedChars[s[i]] = i;
       
               ret = std::max(ret, length);
           }
       
           return ret;
       }
       
   };