算法連載之求解不含有重複字符的最長子串長度

問題

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

示例 1:

輸入: "abcabcbb"

輸出: 3

解釋: 因為無重複字符的最長子串是 "abc"，所以其長度為 3。

示例 2:

輸入: "bbbbb"

輸出: 1

解釋: 因為無重複字符的最長子串是 "b"，所以其長度為 1。

示例 3:

輸入: "pwwkew"

輸出: 3

解釋: 因為無重複字符的最長子串是 "wke"，所以其長度為 3。

暴力求解

枚舉所有字符子串，獲取長度最長的無重複字符子串。

分析程序，匹配在給定字符串中是否有重複字符isRepeating函數的時間複雜度是O(n)。因此，完成算法的時間複雜度是O(n³)；空間複雜度是O(min(n, m))，其中n是字符串的長度，m是相異字符的數量。

從算法分析，如果從 0 到 j-1 是無重複字符子串，第j項元素同前面的任意一個元素重複，則不管第j項後面有無元素，0<=j-1

滑動窗口求解

1）如果從 0 到 j-1 是無重複字符子串，第j項元素同前面的任意一個元素重複，則不管第j項後面有無元素，0<=j-1

2）移動開始索引位置，直到沒有重複元素為止，此時為沒有重複元素的子串，第j項作為結束索引繼續向後移動，直到待判斷的字符串結束為止，判斷是否出現重複。如果出現重複，則繼續重複2）。

滑動窗口算法優化了暴力求解法，當結束索引到第j項出現重複，不再向後繼續判斷，而是移動開始索引，直到沒有重複元素為止，再繼續向後移動結束索引，避免冗餘判斷。

在最壞情況下，字符串所有元素都會被開始索引和結束索引各遍歷一次。時間複雜度是O(2n)=O(n)。空間複雜度是O(min(n, m))，其中n是字符串的長度，m是相異字符的數量。

分析算法發現，當出現一次重複時，我們移動開始索引位置，直到剔除重複元素為止。如果在移動過程中，未剔除重複元素，則一直要移動開始索引。因此，我們可以考慮讓開始索引移動位置一步到位。

優化滑動窗口求解

優化滑動窗口求解方法，當出現判斷字符為重複項時，直接將窗口的開始索引位置置於重複項的下一個元素繼續判斷。

時間複雜度是O(n)。空間複雜度是O(min(n, m))，其中n是字符串的長度，m是相異字符的數量。

性能分析

隨機5000個字符的待匹配字符串進行測試：

The length of longest substring is 42 by Violence solve, using time is 2908 milliseconds.

The length of longest substring is 42 by Sliding Window solve, using time is 2 milliseconds.

The length of longest substring is 42 by Optimizing Sliding Window solve, using time is 2 milliseconds.

通過測試結果分析，移動窗口算法性能優異，時間複雜度是線性增長。