Description:
https://leetcode.com/problems/longest-substring-without-repeating-characters/#/description
Boundary:
when s.size() ==0
Algorithm:
Initially, I just thought about discard the previous longest string and calculate the new string.
However, we cannot discard the whole previous string, the elements may be useful in the following string, such as “dvdf” ‘s result is 3 rather than 2.
Code:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (!s.size()) return 0;
string cur = “”;
string pre = “”;
for (int k = 0; k < s.size();k++)
{
while (cur.find(s[k]) < cur.npos)
{
if (cur.size() >= pre.size())
pre = cur;
cur.erase(cur.begin());
}
cur += s[k];
}
if (cur.size() < pre.size())
return pre.size();
else
return cur.size();
}
};
Tip:
Beats 65.54%. The time complexity is O(n).