Question
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.
Solution
First solution
create an ASCII table, the value of that array is the index of the string.
class Solution {
public:
int k=0, a[128] = { 0 };
int lengthOfLongestSubstring(string s) {
int ans = 0,i,j=0;
for (i = 0; i < s.length(); i++) {
j = max(a[s[i]],j); //此處j為最大的重復字符的索引
ans = max(ans,i-j+1);
a[s[i]] = i+1;
}
return ans;
}
};
Second solution
using an unordered_set as a sliding window and let it iterate through the string.
class Solution {
public:
static int lengthOfLongestSubstring(string s) {
int ans = 0, i = 0, j = 0;
unordered_set<char> set;
for (j; j<(int)s.length();) {
if (set.count(s[j])<=0) { //表中不包含字符
set.insert(s[j++]); //sliding window 表尾后移
ans = max(ans, j - i);
}
else {
set.erase(s[i++]); //sliding window 表頭后移
}
}
return ans;
}
};
Third solution
using an unordered_map as a sliding window and let it iterate through the string.
class Solution
{
public:
static int lengthOfLongestSubstring(string s) {
unordered_map<char, int> map;
int i = 0, j = 0, ans = 0;
for (; i < (int)s.length(); i++) {
if (map.find(s[i]) != map.end())
{
j = max(j, map[s[i]]);
}
ans = max(i - j + 1, ans);
map.erase(s[i]);
map.insert({ s[i],i+1 });
}
return ans;
}
};
