[ leetcode ] 3. Longest Substring Without Repeating Characters

주어진 문자열 중에서 반복 되지 않는 문자로 구성된 sub string중 가장 긴 문자열을 찾는 문제입니다.

map에 각 character별 index위치를 넣어두고, 같은 문자가 발견되면 이미 map에 index가 있다는 의미이므로 구간 길이를 조정해야 합니다.

현재 유효한 구간은 start - end이고 만약 map안의 index가 end보다 작은 경우는 의미가 없으므로, 현재 index가 아직 포함되지 않고 있더라도 end보다 작은 index이면 sub string길이를 비교하여 업데이트합니다.

만약, 그렇지 않고 유효한 길이 안에 같은 문자가 있다면 end 길이를 발견된 index + 1로 업데이트합니다.

매 문자마다 index를 업데이트해주어 linear time complexity에 해결할 수 있습니다.

#include <map>
#define max(a,b)((a) > (b) ? (a) : (b))

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int> index;
        int answer = 0;
        int end = 0;
        for (int start = 0; start < s.length(); start++) {
            if (!index.count(s[start]) || index[s[start]] < end)
                answer = max(answer, start - end + 1);
            else
                end = index[s[start]] + 1;
            index[s[start]] = start;
        }
        return answer;
    }
};