[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.


思路：

hash table经常是一种有效的工具来判断重复，C++的STL中的unordered_map和unordered_set实现了hash table/set的O(1) 查找功能。

用hash table 来存储当前没有重复字符的substring的所有字符(key)以及它们的位置(val)。

假如当前有效substring为：s[k : i-1]

hash table存储了：{s[k], k}, {s[k+1], k+1}, ... {s[i-1], i-1}

当下一个字符s[i]仍然是新字符时，插入即可。而当下一个字符已经存在于hash table中，则hash table记录了S[i]字符上一次出现的坐标j (k<=j<i)，而S[j+1:i]形成了新的有效substring。这里需要额外操作的是在hash table中删除{s[k], k} ... {s[j], j}，因为它们已经不在新的substring中。

如何在hash table中删除s[k:j]？当然可以遍历hash table来检查每个坐标，但如果hash table很大则会很浪费。所以我们需要记录每个有效substring的起始位置k，用双指针+hash table来解决。

复杂度分析：

空间复杂度最差情况显然是O(n)：当整个s没有重复时。

时间复杂度看似复杂，因为我们并不知道每次对hash table删除的复杂度。但对于每个s[i]来说，最多只会插入/更新hash table一次，以及被删除一次。不存在被多次插入删除的可能。所以最终复杂度仍然是O(n)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: int lengthOfLongestSubstring(string s) { unordered_map<char,int> ht; int maxLen = 0, curLen = 0, start = 0; for(int i=0; i<s.size(); i++) { if(ht.count(s[i])) { for(int j=start; j<ht[s[i]]; j++) ht.erase(s[j]); start = ht[s[i]]+1; curLen = i-ht[s[i]]; } else { curLen++; } ht[s[i]] = i; maxLen = max(maxLen,curLen); } return maxLen; } };