The problem to be solved today is the second problem in the lis :Ltongest Substring Without Repeating Characters. The problem description is pretty short.
Given a string
s, find the length of the longest substring without repeating characters.
The first thought came up to me is solving by mighty hash map. Hash map can record enough information for us to decide that current character if existed and its index.
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> mp;
int ans = 0, cur = 0, start = 0;
for(int i = 0; i < s.size(); i++){
if(mp.find(s[i]) != mp.end()){
// repeat
int j;
for(j = start; j <= mp[s[i]]; j++){
mp.erase(s[j]);
}
start = j;
mp[s[i]] = i;
ans = max(ans, cur);
cur = i - j + 1;
}else{
// no repeat
mp[s[i]] = i;
cur++;
}
}
ans = max(ans, cur);
return ans;
}This solution is quite straight-forward by get the bad performance, it only faster than 38.16% C++ submission and memory usage only less than 26.26% C++ submission. Let’s us find better solution in discussion.
In discussion, I found a good answer for this question:
vector<int> dict(256, -1);
int maxLen = 0, start = -1;
for (int i = 0; i != s.length(); i++) {
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxLen = max(maxLen, i - start);
}
return maxLen;It replace hash map with a vector which is enough for ASCII character. Instead of using erase , it maintain current section and slide it.