[C] LeetCode 3. Longest Substring Without Repeating Characters

문제(원문)

문제(번역)

문자열 s가 주어졌을 때 중복되는 문자가 없는 가장 긴 부분 문자열의 길이를 구해라.

단, s는 영어문자, 숫자, 기호, 공백이 들어갈 수 있다.

접근 방법

알파벳이면 26 정도로 범위를 잡으면 되지만, 이는 숫자, 기호, 공백이 모두 들어가서 어떻게 해야할지 감이 안잡혔다.

 

외부 라이브러리나 직접 dict 같은걸 구현하기에는 코드가 너무 길어질 것 같아서 고민하다가,

아스키코드의 범위가 0부터 127이라는 것을 깨달았다. 

 

즉 아스키 코드 범위에 대해서만 flag를 지정하고 매번 겹치는 문자가 있는지 검사하는 방법으로 코드를 구현했다.

 

소스 코드

char map[128] = {0};
void initMap(){
    for(int t=0;t<128;t++) map[t] = 0;
}
int lengthOfLongestSubstring(char* s) {
    int maxL = 0;
    int len = 0; while(s[len] != '\0') len++;
    for(int i = 0; i<len;i++) {
        initMap();
        int j  = i, cnt = 0;
        while(s[j] != '\0') {
            if(map[s[j]] == 0) { map[s[j]] = 1; cnt++; }
            else break;
            j++;
        }
        maxL = (maxL < cnt) ? cnt : maxL;
    }
    return maxL;

}

C언어로 작성한 코드인데, 아래와 같은 실행결과가 나왔다.