Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 3:
Input: "pwwkew"
Output: 3
Explanation: 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.
// int vector served as a hash table to record last occurrence index of char
int lengthOfLongestSubstring(string s) { // time: O(n); space: O(1)
vector<int> record(128, -1); // last occurrence index
int start = -1, res = 0;
for (int end = 0; end < s.length(); ++end) {
start = max(start, record[s[end]]);
record[s[end]] = end;
res = max(res, end - start);
}
return res;
}
// Sliding window
int lengthOfLongestSubstring(string s) { // time: O(n); space: O(1)
int begin = 0, end = 0, d = 0, counter = 0;
vector<int> record(128, 0);
while (end < s.length()) {
if (record[s[end++]]++ > 0) {
counter++;
}
while (counter > 0) {
if (record[s[begin++]]-- > 1) {
counter--;
}
}
d = max(d, end - begin);
}
return d;
}