3. Longest Substring Without Repeating Characters

Solution 1 直覺做法

int check(char * myarray, char c){
    
    int val = (int)c;
    
    if(myarray[val]){
        return 1;//char existed
    }
    else{
        return 0;//
    }
}

void addfunc(char * myarray, char c){
    int val = (int)c;
    myarray[val]++;
}

int lengthOfLongestSubstring(char * s){
    int s_len = 0,ans = 0, status =0,count = 0, max = 0;
    int i, j;
    char* tmp = s;
    if(!s)
        return 0;
    while(*tmp){
        s_len++;
        tmp++;
    }
    char* myarray = calloc(1000,sizeof(char));
    
    for(i=0; i<s_len; i++){
        for(j=i;j<s_len;j++){
            //check first
            status = check(myarray, s[j]);
            if(status == 0){
                count++;
                if(max < count){
                    max = count;
                }
                addfunc(myarray, s[j]);
                
            }
            else{
                if(max < count){
                    max = count;
                }
                //printf("count = %d\n",count);
                count = 0;
                //array reset
                for(int z =0;z<1000;z++)
                    myarray[z] = 0;
            }
        }
        count =0;
        for(int z =0;z<1000;z++)
            myarray[z] = 0;
        
    }
    if(max < count){
        max = count;
    }
    return max;
}

很可惜，超時了
複雜度

$O(N^2)$

Solution 2 Hash table

int lengthOfLongestSubstring(char * s){
    if(!s)
        return 0;
    int *my_array = malloc(128 * sizeof(int));
    int max =0,s_len=0,start = 0;
    char* tmp = s;
    while(*tmp){
        tmp++;
        s_len++;
    }
    for(int i=0;i<128;i++)
        my_array[i] = -1;
    for(int i = 0; i<s_len; i++){// in substring
        if(my_array[s[i]]>=start){
            start = my_array[s[i]]+1;
            my_array[s[i]] = i;
        }
        else{// not in substring
            my_array[s[i]]=i;
            max = (max<(i-start+1))?(i-start+1):max;
        }
    }
    return max;
}