[Leetcode] 3. Longest Substring Without Repeating Characters

Identifying the Problem

주어진 문자열 s에서 중복되는 문자가 없는 Substring의 길이를 구한다.

Sourcecode

int lengthOfLongestSubstring(char * s)
{
    int letterMap[128] = {0};
    int max = 0;
    char* start = s;
    char* end = s;
    
    while(*end)
    {
        if(letterMap[*end] != 0) //탐색 값이 중복일 때
        {
            max = (end-start) > max ? (end - start) : max;
            // 중복을 찾은 지점과 처음 지점의 차이 = Substring 길이
            // Substring가 max보다 크면 max에 단어길이 저장
            while(*start != *end)
            {
                letterMap[*start] = 0; //Substring에 있던 글자들 0으로 초기화
                start++; //Substring 의 탐색지점 이동 ex(abc 였으면 a->b->c)
            }
            
            start++; //시작점을 중복이었던 부분으로 이동
            
        }
        
        else //탐색 값이 중복 아닐 때
        {
            letterMap[*end] = 1; //해당 문자가 있었다고 표시
        }
        
        end++; //탐색 값 다음 위치로
    }
    return (end-start) > max ? (end - start) : max;
    // 중복이었던 경우가 아예 없었더라면, end-start가 max값이 됨
}

New things learned

• 포인터의 위치차로 단어의 길이를 구하는 방법이 신박했다.
• 시간복잡도를 줄이는 방법 중 하나는 사용하는 메모리를 늘리는 것이다.
• O(n₃)인 풀이에서 중복인 부분을 판단하는데 반복문을 사용하는데,
  이 풀이에서 letterMap을 사용해 중복이었는지 아닌지 판단했다.