[LeetCode] [Medium] Longest Substring Without Repeating Characters

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.

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;
    }
};