[LeetCode] [Medium] Longest Substring Without Repeating Characters
2021. 3. 18. 23:03ㆍ알고리즘/LeetCode
1. Problems
Given a string.
Find max length of substring without repeating characters.
2. sol
I check all ascii for int array.
Visited array has index of first finded index.
and if find repeating char, Initialize all elements in front of first fineded index.
This time complexity is O(N)
because inner for statement operate total maximum n.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int visited[127];
int answer = 0;
memset(visited, -1, sizeof(visited));
for(int i = 0, count = 1; i < s.size(); i++, count++)
{
if(visited[s[i]] != -1)
{
int startIndex = i - count;
count -= (visited[s[i]] - startIndex);
for(int j = visited[s[i]]; j > startIndex; j--)
visited[s[j]] = -1;
}
visited[s[i]] = i;
answer = max(answer, count);
}
return answer;
}
};
|
cs |
'알고리즘 > LeetCode' 카테고리의 다른 글
[LeetCode] [C++] Reverse Integer (0) | 2021.05.11 |
---|---|
[LeetCode] [Medium] ZigZag Conversion (0) | 2021.03.21 |
[LeetCode] [Medium] Longest Palindromic Substring (dp) (0) | 2021.03.20 |
[LeetCode] [Medium] Add Two Numbers (linked list) (0) | 2021.03.17 |
[LeetCode] [easy] Two Sum (brute-force, map) (0) | 2021.03.16 |