# I Post My O(n^2) Solution Here(It luckily got accepted). Anybody has an O(n) solution?

• ``````class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> table;
int tmpCnt = 0;
int maxCnt = 0;
for(int i = 0; i < s.length(); i++){
auto iter = table.find(s[i]);
if(iter == table.end()){
tmpCnt++;
}
else{
table.clear();
tmpCnt = 1;
int j = i-1;
while(s[j]!=s[i]){
table.emplace(s[j]);
j--; tmpCnt++;
}
}
table.emplace(s[i]);
if(tmpCnt > maxCnt) maxCnt = tmpCnt;
}
return maxCnt;
}
};
``````

I tried to use a Unordered_set to keep track of the previous char I encountered. When I encounter a char that has previously appeared, I will firstly clear the content of the unordered_set, then push all the char behind the char that appeared twice back into the unordered_set. At the meantime, I am storing my counting result to a counter variable and finally use this variable to update my 'max' value.

But I am feeling terrible about this O(n^2) method. It would be great if you guys can give me some inspiration on a O(n) method.

• Your algorithm's runtime complexity is in fact O(n) and not O(n2). In your code, the number of iteration is in the order of m x n, where m is the number of unique characters that could contain in s. Since the number of unique ascii characters is constant (m = 255), the complexity boils down to the order of O(n).

That being said, there exists a more efficient O(n) algorithm which does at most 2n iterations. You can read about the in-depth analysis I wrote here.

Side note:
I have improved the test case such that your code is judged as Time Limit Exceeded now.

• Hey man thanks for your kind reply! I was one step further for your proposed answer. Recording start point and end point of the substring using two variables was something I should definitely go through my mind.

• LOL for the new test case. it is destructive

• This post is deleted!

• This post is deleted!

• ``````class Solution {
public:
int lengthOfLongestSubstring(string s) {
int arr[256]={0};
int k = s.length();
int start=0,count=0,max=0,i;
for(i=0;i<s.length();i++)
{
if(arr[s[i]]&&arr[s[i]]>=start )
{
start=arr[s[i]];
count=i-start+1;
arr[s[i]]=i+1;
}

else
{
arr[s[i]]=i+1;
++count;
}

if(count>max)
max=count;

}
return max;
}
};
``````

its a O(n) solution which determines the answer in single pass.
m using a char buffer to store the index of the characters in the current substring,
if the current character is already present in the current substring, we start a new substring.

we update 'start' of a new substring
as previous index of the current character + 1

• ``````class Solution {
public:
int lengthOfLongestSubstring(string s) {
int count(0), index(0), res(0);
unordered_map<char, int> dup;
for (int i = 0; i < s.length(); i++){
if (dup.count(s[i])&&dup[s[i]]>=index){
index = dup[s[i]];
count = i - index - 1;
}
dup[s[i]] = i;
count++;
res = std::max(res, count);
}
return res;
}
};
``````

I use a int index to record last repeated char's position.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.