4ms C solution beats 95%, code. use array int h[128];


  • 2
    A
    int lengthOfLongestSubstring(char* s) {
      int h[128];
      int beginCurr=0;
      int max=0,i=0;
      for(i=0;i<128;i++){
        h[i]=-1;
      }
      i=0;
      while(*s){
        //check whether current character has been seen since beginCurr
        if(h[*s]>=beginCurr){
          if(i-beginCurr>max)
            max=i-beginCurr;
          beginCurr=h[*s]+1;
        }else{
          if(i-beginCurr+1>max)
            max=i-beginCurr+1;
        }
        h[*s]=i;
        i++;
        s++;
      }
      return max;
    }
    

  • 0
    C

    Hello, why do you use array int h[128] rather than h[256]?


  • 0
    S

    @colonboy Typically if someone uses an int array for indexing chars, the assumption is usually all characters are ascii. The ascii table consists of 128 chars so h[128] is always used. Obviously if the char set for the input is not ascii, then 128 elements may be too much or too little and you need to find the right size to initialize your array.


  • 0
    Z
    This post is deleted!

  • 0
    Z

    Could u explain the basic idea of your code??


  • 0
    L

    Are you sure it cost only 4ms ???


  • 0
    L

    Your solution now runs in 6ms. Same as mine.
    I guess it's always easier to read one's own code.

    int lengthOfLongestSubstring2(char* s) {
    
            int rc = 0, start=0, end=1;
            
            int occur[128];
            
            for(int i = 0; i< 128; i++)
            {
                occur[i] = 0;
            }
            
            if(s == NULL || s=="")  return 0;
            
            occur[s[start]] = 1; //!!!
            
            while(s[start] != '\0')
            {
                while(s[end] != '\0')
                {
                    if(!occur[s[end]])
                    {
                        occur[s[end]] = 1;
                        end++;
                    }
                    else
                    {
                        int cur = end - start;
                        if(cur > rc)
                        {
                            rc = cur;
                           // printf("end:%d start:%d\n", end, start);
                        }
                        
                        while(s[start] != s[end])
                        {
                            occur[s[start]] = 0;
                            start++;
                        }
                        
                        //!!!
                        start++;
                        end++;
                        
                        break;
                    }
                }
                
                if(s[end] == '\0')
                {
                    int cur = end - start;
                    if(cur > rc) 
                    {
                        rc = cur;
                        //printf("end:%d start:%d\n", end, start);
                    }
                    break;
                }
            }
            
            return rc;
    }
    
    

  • 0
    L

    @alejandroerickson

    Finally understood your code.
    Yours h[128] stores the posintion of char i's last ocurrence, which is smarter than mine.

    Though I think the else part in the while loop can be moved out, because the longest sub-string ends either when we meet a duplicate or at the end of original string.

    int lengthOfLongestSubstring(char* s) {
      int h[128];
      int beginCurr=0;
      int max=0,i=0;
      for(i=0;i<128;i++){
        h[i]=-1;
      }
      i=0;
      while(*s){
        //check whether current character has been seen since beginCurr
        if(h[*s]>=beginCurr){
          if(i-beginCurr>max)
            max=i-beginCurr;
          beginCurr=h[*s]+1;
        }
        h[*s]=i;
        i++;
        s++;
      }
      
       if(i-beginCurr>max)
       {
            max=i-beginCurr;
       }
       
      return max;
    }
    

Log in to reply
 

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