O(n) solution write in C ------8ms with explanations


  • 0
    Q
    int lengthOfLongestSubstring(char* s) {
    // if(s[0]=='\0') return 0;
    int position[256];//store location
    for(int i=0;i<256;i++){
        position[i]=-1;
    }
    int index=0;
    int repeatIndex=0;
    int maxLength=0;
    while(s[index]!=0){
        if(position[s[index]]!=-1)
        {
            int tempLength=index-repeatIndex;
            if(maxLength<tempLength){
                maxLength=tempLength;
            }
            int tempRepeatIndex=repeatIndex;
            repeatIndex=position[s[index]]+1;
            if(repeatIndex<tempRepeatIndex){
                repeatIndex=tempRepeatIndex;
            }
        }
        position[s[index]]=index;
        int tempLength=index-repeatIndex+1;
        if(maxLength<tempLength){
            maxLength=tempLength;
        }
        index++;
    }
    
    return maxLength;
    }
    

    Assume the string is like this:

    "abcdefaghijk | lmn"

    so first step is set up a indicator to traverse the character of the string。we need a loop, while is fine,so we write the traverse character code like follows:

    int index=0;
    while(s[index]!=NULL){
        index++;
    }
    

    we also need another indicator to track the repeat charactor .why?because we need to caculate the length of substring like follows:(we treat the "|" as virtual seperator)

     1,|abcdefg|a  the length is 7
     2,a|bcdaefghijklmn|  the length is 14
     3, |ab|ba the length is 2
    

    so we continue:

    int index=0;
    int repeatIndex=0;// former seperator
    int maxLength=0;//we need to track the max length of substring 
    while(s[index]!=NULL){
        index++;
    }
    

    all variable was set up. for the index's string ,how do we get the longest substring?

            index
              |
        abcde f g   //we need to traverse abcde to find the same f .
    

    so we need to traverse the the charactor before index's charactor of the string.
    we continue write the code:

    int index=0;
    int repeatIndex=0;// former seperator
    int maxLength=0;//we need to track the max length of substring 
    while(s[index]!=NULL){
        for(int i=0;i<index;i++){
            if(s[i]==s[index]{
                int length=index-i;
            }
        index++;
    }
    

    so the code is to caculate the length from begin to the index like follows:

         index
           |
    aabcdefa
    

    we get the two result about length

     1 aabcdef //the length is 7
     2 abcdef //the length is 6
    

    but what we really want is 2.
    so we need to use the repeatIndex variable to track this.
    the code is like followings(only for-loop code)

    for(int i=repeatIndex;i<index;i++){//we start from not 0 but repeatIndex ,beacause we want the length       between repeatIndex  and index. ex:   ab|cefghc|
    
         if(s[i]==s[index]){
                int tmp=index-repeatIndex; //the length.
                if(maxLength<tmp){
                    maxLength=tmp;
                }
            repeatIndex=i+1; //repeatIndex move forward one step
        }
    

    this piece of code only solve the situation like this : |abcdefgh|a
    I will give you the entire code :

    int lengthOfLongestSubstring(char* s) {
    if(s[0]=='\0'){
        return 0;
    }
    //追踪下一个字符
    int index=0;
    //如果重复,把第一个重复的字符向前移一格
    int repeatIndex=0;
    //字符的最大长度
    int maxLength=0;
    //具体思路:设置两游标,第一个游标取下一个字符,第二个游标取重复字符,取两者的差为长度
    do{
        //初始化maxLength
        for(int i=repeatIndex;i<index;i++){
            if(s[i]==s[index]){
                int tmp=index-repeatIndex;
                if(maxLength<tmp){
                    maxLength=tmp;
                }
                repeatIndex=i+1;
            }
        }
        
        int tmpLength=index-repeatIndex+1;
        if(maxLength<tmpLength){
           maxLength=tmpLength; 
        }
        index++;
    }while(s[index]!='\0');
    
    //如果字符的长度为1
    if(index==1){
        return 1;
    }
    
     return maxLength;   
    }
    

    because of two loop .the estimate time is O(n^2)

    so we get the first version.Lets do some paper work. we see that the longest substring is less than 256 in any string. because there is only 256 ASCII. Let continue considering about the repeatIndex.Why we want the for loop ? we just want to track the index of the repeatIndex variable in the string .ex: to caclulate the string "wbcaadefghia",we just want the position of the a (a position 3rd ,4th,the 4th position is important because we use this to caculate the longest substring.) so we define a array to track a position (because one character have several position like "aaab",a has 3 position 0,1,3) of every possible character in the string.So we define a int 256 size array like follows:

    int position[256];//store location
        for(int i=0;i<256;i++){
            position[i]=-1;
        }
    

    but you may wondering that one item of the array can only store one position.but some character in a string has serveral locations. So we have to pick the important position to store. (ex: "aaaabcdefa" the 3rd
    a is import beacause we use it to caculate the longest substring).

    we use the following sentence to init the position array:
    because one character is the int number between 0~255.like position['a']=position[97].
    position[s[index]]=index;

    we write the code in while-loop as follows:

    if(position[s[index]]!=-1) //we check the array ,if position['somecharactor'] is not equal -1, it conclude that s[index] charactor was initialized before. is like that aabc ,position[a]=0,when get the 2nd a,the position[a] =0 not -1.
    {
        int tempLength=index-repeatIndex;//we calculate length between two same character .
        if(maxLength<tempLength){
            maxLength=tempLength;
        }       
        repeatIndex=position[s[index]]+1;//the move the repeatIndex forward for one step.as:the string "abcdaefghijklmn" when the index come to 'a' after d,we move the repeatIndex to 'b' and go on.
    
    }
    
    position[s[index]]=index;
    
    int tempLength=index-repeatIndex+1;//when the several substring has no same character.
    if(maxLength<tempLength){
        maxLength=tempLength;
    }
    

    this works fine but one situation like "abba"
    when the index come to the last a.repeatIndex=position[s[index]]+1=> repeatIndex=position[a]+1=1,so
    the result is 3, this is not right .because at "abb|a"the repeat index is 2, so we just to ensure that the replaceIndex can not go back. so add follow code:

    int tempRepeatIndex=repeatIndex;
            repeatIndex=position[s[index]]+1;
            if(repeatIndex<tempRepeatIndex){
                repeatIndex=tempRepeatIndex;
            }
    

    This is how I solve this problem .Hope this can help someone newer just like me.Learn how to solve problem is far important that a results.Thanks.
    sorry about terrible English.I am just a newer to the English and programming.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.