[LeetCode]3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

題意：

給定一個(gè)字符串，找出最長的無重復(fù)的連續(xù)字串。就比如"pwwkew"的最長無重復(fù)連續(xù)字串是"wke"。

最易想到的方法就是字符串逐一開始查找，第一個(gè)字符串找到最長的字串，依次找出，取最大值即可。

由于有256個(gè)字符，故定義了個(gè)257長度的數(shù)組，足以存下所有字符。

思路

1）定義字符數(shù)組，并把256個(gè)的值都置為零。

2）逐個(gè)查找字符，如果未出現(xiàn)過，即把該下標(biāo)對(duì)應(yīng)的數(shù)組值置為一。若該下標(biāo)值已經(jīng)是一了，則返回，

3）重置全部數(shù)組元素元素為零，從下個(gè)下標(biāo)開始繼續(xù)查找不重復(fù)字串。

4）返回最大字串長度即可。

#define CHARACTERS 257

int lengthOfLongestSubstring(char* s) 
{
    if ( !s )
    {   
        return 0;
    }
    
    int character[CHARACTERS] = { 0 };
    int len = strlen(s);
    
    int cnt  = 0;
    int size = 0;
    int maxLen = 0;
    int index = 0;
    for ( index = 0; index < len; index++ )
    {
        size = 0;
        for ( cnt = 0; cnt < CHARACTERS; cnt++ )
        {
            character[cnt] = 0;
        }
        
        for ( cnt = index; cnt < len; cnt++ )
        {
            /* pwwkew */
            int value = *(s + cnt);
            if ( character[value] == 0 )
            {
                size += 1;
                character[value] = 1;
            }
            else
            {
                break;
            }
        }
        
        if ( size > maxLen )
        {
            maxLen = size;
        }
    }
    
    return maxLen;
}