[leetcode] 3. Longest Substring Without Repeating Characters

문제

Given a string, find the length of the longest substring without repeating characters.

 

풀이

Sliding Window 방식을 사용한다. 

반복되는 문자가 없는 Window를 계속 관리해준다.

 

새 문자가 window에 추가될 때, 이 문자가 window에 없는 문자면 그냥 window를 늘려가면 되고,

이미 등장한 문자면 현재 추가될 문자의 가장 최신 위치를 찾아서, 그 앞까지를 새로운 window로 정하면 된다.

 

이를 빠르게 계산하기 위해 알파벳별로 최근에 등장한 위치를 저장해두면서 관리한다.

이를 계산해놓으면 새 문자가 추가될때, 해당하는 window를 O(1)에 계산할수 있다.

 

Time Complexity : $O(n)$

 

코드

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int l=s.length(),ans=0;
        int index[128]={0,};
        
        for(int i=0,j=0;j<l;j++)
        {
            i = max(index[s[j]],i);
            ans = max(ans, j-i+1);
            index[s[j]] = j+1;
        }
        return ans;
    }
};