-
Notifications
You must be signed in to change notification settings - Fork 42
/
Copy path3. Longest Substring Without Repeating Characters.cpp
141 lines (127 loc) · 4.37 KB
/
3. Longest Substring Without Repeating Characters.cpp
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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
//Runtime: 84 ms, faster than 16.28% of C++ online submissions for Longest Substring Without Repeating Characters.
//Memory Usage: 13.3 MB, less than 31.84% of C++ online submissions for Longest Substring Without Repeating Characters.
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int ans = 0;
int start = 0, end = 0;
map<char, int> position;
while(end < s.size()){
ans = max(ans, end-start+1);
position[s[end]] = end;
// cout << start << " " << end << endl;
// for(auto it = position.begin(); it != position.end(); it++){
// cout << it->first << " " << it->second << " | ";
// }
// cout << endl;
if(end+1 < s.size()){
if(position.find(s[end+1]) == position.end()){
end++;
}else{
int newStart = position[s[end+1]]+1;
for(int i = start; i < newStart; i++){
position.erase(s[i]);
}
start = newStart;
end++;
// position.clear();
}
}else{
break;
}
}
return ans;
}
};
//Brute Force
//TLE
//894 / 987 test cases passed.
//time: O(N^3), space: O(min(size_of_string, size_of_charset))
class Solution {
public:
bool allUnique(string& s, int start, int end){
set<char> chars;
for(int i = start; i <= end; i++){
auto res = chars.insert(s[i]);
if(res.second == false) return false;
}
return true;
};
int lengthOfLongestSubstring(string s) {
int ans = 0;
for(int i = 0; i < s.size(); i++){
for(int j = i; j < s.size(); j++){
if(allUnique(s, i, j)){
ans = max(ans, j-i+1);
}
}
}
return ans;
}
};
//Approach 2: Sliding Window, using set
//Runtime: 80 ms, faster than 16.88% of C++ online submissions for Longest Substring Without Repeating Characters.
//Memory Usage: 13.4 MB, less than 30.85% of C++ online submissions for Longest Substring Without Repeating Characters.
//time: O(N), space: O(min(size_of_string, size_of_charset))
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
set<char> chars;
int ans = 0, i = 0, j = 0;
while(i < n && j < n){
// cout << i << " " << j << endl;
if(chars.find(s[j]) == chars.end()){
//move head forward
chars.insert(s[j]);
ans = max(ans, j-i+1);
j++;
}else{
//move tail forward
chars.erase(s[i]);
i++;
}
}
return ans;
}
};
//Approach 3: Sliding Window Optimized
//Runtime: 44 ms, faster than 27.74% of C++ online submissions for Longest Substring Without Repeating Characters.
//Memory Usage: 8.3 MB, less than 100.00% of C++ online submissions for Longest Substring Without Repeating Characters.
//time: O(N), space: O(min(size_of_string, size_of_charset))
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
map<char, int> position;
int ans = 0;
for(int i = 0, j = 0; j < n; j++){
if(position.find(s[j]) != position.end()){
i = max(i, position[s[j]]+1);
}
ans = max(ans, j-i+1);
position[s[j]] = j;
}
return ans;
}
};
//Approach 4: Sliding Window Optimized, further optimized
//Runtime: 8 ms, faster than 93.51% of C++ online submissions for Longest Substring Without Repeating Characters.
//Memory Usage: 7.8 MB, less than 100.00% of C++ online submissions for Longest Substring Without Repeating Characters.
//time: O(N), space: O(size_of_charset)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.size();
vector<int> position(128, -1);
int ans = 0;
for(int i = 0, j = 0; j < n; j++){
if(position[s[j]] != -1){
i = max(i, position[s[j]]+1);
}
ans = max(ans, j-i+1);
position[s[j]] = j;
}
return ans;
}
};