본문 바로가기

C

c++ leetcode O(N) solution Longest Substring Without repetition

code >>

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
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int total_size = (int)s.size();
        if (total_size == 1)
        {
            return 1;
            
        }
        if (total_size == 0)
        {
            return 0;
        }
        unordered_map<charint> char_index;
        int max_length = 0;
        int d = 1;
        int i = 0;
        char_index[s[i]] = 0;
        for (i=1; i<total_size; i++)
        {
            if ((char_index.count(s[i])==0|| (char_index[s[i]]<i-d))
            {
                d++;
            }   
            else
            {
                d = i - char_index[s[i]];
            }
            char_index[s[i]] = i;
            if (d > max_length)
            {
                max_length = d;
            }
            
        }
        return max_length;
    }
};