Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
Two versions:
No.1 Using Hashmap
Time complexity is O(N*m), N is the size of the string s, m is the max size of the substring without repeating characters. This method is very easy to understand but low efficient.
int lengthOfLongestSubstring(string s) {
int maxLength = 0;
for(int i = 0; i < s.length(); i++){
unordered_map<char,int> hash;
int j = i;
for(; j < s.length(); j++){
hash[s[j]]++;
if(hash[s[j]] > 1) break;
}
maxLength = max(maxLength, j - i);
}
return maxLength;
}
No.2 Using vector
The key idea there is that before we start traverse the string, we use a vector to store each character's newest position we have seen. From the beginning, if we have not met a duplicate character, we keep update the index from -1 to their index. When we see the first duplicate, we update our start position to the character's previous position we have stored in the vector so as to find another substring without duplicate characters.
Time complexity is O(N), much more efficient!
int lengthOfLongestSubstring(string s) {
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;
}
