Finding Length of Longest Substring without Repeating Characters in C in Linear Time

出處

原理

走訪字串中每個字元，若當前被掃瞄字元沒有被走訪過則暫存到陣列中，目前長度加1，否則判斷當前被掃瞄字元是否在不重複字元的子字串中，若不在則目前長度加1，否則檢查最大長度與目前長度，若目前長度大於最大長度就將最大長度設定為目前長度，並且移動不重複字元子字串的起始點到重複字元的下一個字元，例如輸入為"dxdy"，遇到第二個d而且d已經在不重複字元子字串"dx"中，則不重複字元子字串起始點從d移動到x，例如輸入為"pwwkew"，遇到第二個w而且w已經在不重複自原子字串"pw"中，則不重複自原子字串起始點從p移動到第二個w，最後重設目前長度，長度應為新的不重複字元子字串起始點算到當前被掃瞄字元，走訪完所有字元後的目前長度再跟最大長度比較決定最大長度。

實作

#define NUM_CHAR 256

int hash(char x)
{
    return x % NUM_CHAR;
}

int length_of_longest_substring(char * str)
{
    char visited[NUM_CHAR] = {0};
    char temp[NUM_CHAR] = {0};
    char * current_scanned = NULL;
    char * nrcs_start = NULL;  // nrcs: non-repeating character substring
    int key = 0;
    int cur_length = 0;
    int max_length = 0;
    
    current_scanned = s;
    nrcs_start = str;
    while (*current_scanned != '\0')
    {        
        key = hash(*current_scanned);
        if (visited[key] != *current_scanned)
        {
            visited[key] = *current_scanned;
            cur_length++;
            goto end;
        }
        
        strncpy(temp, nrcs_start, cur_length);
        if (!strchr(temp, *current_scanned))
        {
            cur_length++;
            memset(temp, 0, NUM_CHAR);
            goto end;
        }
        
        memset(temp, 0, NUM_CHAR);
        
        if (cur_length > max_length)
            max_length = cur_length;

        while (*nrcs_start != *current_scanned)
            nrcs_start++;
        nrcs_start++;
        
        cur_length = current_scanned - nrcs_start + 1;

end:
        current_scanned++;
    }

    if (cur_length > max_length)
        max_length = cur_length;
    
    return max_length;
}