-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path3.cpp
More file actions
67 lines (61 loc) · 1.86 KB
/
3.cpp
File metadata and controls
67 lines (61 loc) · 1.86 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*************************************************************************
> File Name: 3.cpp
> Author: Alan
> Mail: [email protected]
> Created Time: Sun 08 Nov 2015 04:07:44 AM PST
> Problem Name: Longest Substring Without Repeating Characters
> Difficulty: Medium
> Description:
Given a string, find the length of the longest substring without repeating characters. For
example, the longest substring without repeating letters for "abcabcbb" is "abc", which the
length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
Subscribe to see which companies asked this question
************************************************************************/
#include<iostream>
#include<vector>
using namespace std;
class Solution
{
public:
int lengthOfLongestSubstring(string s)
{
/*
//Solution1: 140ms
auto len=s.size();
int i,j,maxx=0;
set<int> exam;
for(i=0,j=0;j<s.size();j++){
while(exam.find(s[j])!=exam.end()){
exam.erase(s[i]);
i++;
}
exam.insert(s[j]);
maxx=max(maxx,j-i+1);
}
return maxx;
*/
vector<int> index(300, -1);
int len = s.size(), tmp = 1, maxx = 1;
if(len == 0)
return 0;
index[s[0]] = 0;
for(int i = 1; i < len; i++)
{
int lastApp = index[s[i]];
if(lastApp == -1)
tmp++;
else
tmp = min(tmp + 1, i - lastApp);
index[s[i]] = i;
maxx = max(maxx, tmp);
}
return maxx;
}
};
int main()
{
string str("abcabcbb");
Solution sol = Solution();
int len = sol.lengthOfLongestSubstring(str);
cout << "The max length of substring without repeating characters is: " << len << endl;
}