【LeetCode】3. 無重複字元的最長子串

題目：

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

示例：

給定 "abcabcbb" ，沒有重複字元的最長子串是 "abc" ，那麼長度就是3。

給定 "bbbbb" ，最長的子串就是 "b" ，長度是1。

給定 "pwwkew" ，最長子串是 "wke" ，長度是3。請注意答案必須是一個子串，"pwke" 是 子序列 而不是子串。

思路：

1. 從前往後依次掃描字元串，初始化最長字元串長度是length_max = 0。不含重複元素的子串初始坐標是start = 0
2. 如果掃描到第j個字元 c, mark[c] = -1，那麼繼續往後掃描，並且更新mark[c] = j
3. 如果掃描到第j個字元c，mark[c] != -1,這個時候分兩種情況，

• 第一種情況是這個字元之前雖然出現過了，但是它在此次子串的起始位置之前，也就是說mark[c] < start。那麼更新mark[c] = j
• 第二種情況是mark[c] >= start，那麼就代表c之前出現了，並且出現的位置在當前子串中。
• 那麼我們會得到一個新的長度length = j - mark[c], 比較length與length_max，如果length > length_max, 那麼更新length_max = length。
• 並且更新start = mark[c] + 1
• 更新mark[c] = j

舉個例子，對於"abcabcbb"，按照上面的步驟掃描,

• 掃描到a時，設置mark[97] = 0,
• 依次設置mark[98]=1, mark[99] = 2,
• 當掃描到第四位上的a時，發現mark[97] != -1，並且mark[97] 是0，mark[97] >= start，
• 所以會產生第一個沒重複的子串的長度，3 - 0 = 3， 更新length_max = 3
• 更新start = mark[97] + 1 = 1
• 更新mark[97] = 3
• 繼續掃描b,發現mark[98] != 0，mark[98]是1，mark[98] > start，所以產生下一個長度length = 4 - 1 = 3, length_max 還是3.
• 後面掃描類似，此處不再贅述

代碼

以下是C++代碼實現

class Solution {public: int lengthOfLongestSubstring(string s) { if(s.length() <= 1)return s.length(); int start = 0, length_max = 0, length = 0, j = 0; int mark[256] = {}; std::fill_n(mark, 256, -1); for(; j < s.length(); j++) { if(mark[s[j]] != -1 && mark[s[j]] >= start) { length_max = length_max > j - start? length_max: j - start; start = mark[s[j]] + 1; } mark[s[j]] = j; } length_max = length_max > s.length() - start? length_max: s.length() - start; return length_max; }};

以下是python解法：

class Solution: def lengthOfLongestSubstring(self, s): """ :type s: str :rtype: int """ hash_table = [] for i in range(256): hash_table.append(-1) max_res = 0 begin_index = 0 for i in range(len(s)): if hash_table[ord(s[i])] != -1 and hash_table[ord(s[i])] >= begin_index: max_res = max(max_res, i - begin_index) begin_index = hash_table[ord(s[i])] + 1 hash_table[ord(s[i])] = i max_res = max(max_res, len(s) - begin_index) return max_res

推薦閱讀：