C solution, 3ms


  • 0
    S
    int lengthOfLongestSubstring(char* s) {
      int maxLen = 0, prevMaxLen = 0, prevIndexOf[128];
    
      bzero(prevIndexOf, sizeof(prevIndexOf));    
      for (char *c = s; *c; c++) {
        int idx = c - s + 1;   // Add 1 to the index since prevIndexOf is initialized with zeros
        int candidateLen = idx - prevIndexOf[*c];
        int curMaxLen = (++prevMaxLen < candidateLen) ? prevMaxLen : candidateLen;
        prevIndexOf[*c] = idx;
        
        if (curMaxLen > maxLen) {
          maxLen = curMaxLen;
        }
        prevMaxLen = curMaxLen;
      }
            
      return maxLen;
    }
    

  • 0
    J

    wow ! amazing algorithm!!!
    could you tell me how you came up this algorithm?plz


  • 0
    S

    Thanks @JasonZWJ

    This was inspired by Kadane's algorithm for the maximal subarray problem.
    The basic idea is that the length of the longest substring ending at position i is the lesser of

    • length(longest substring ending at position i - 1) + 1
    • i - prevIndexOf[*c] i.e. the number of characters since the previous occurrence of the character at position i

    So we can use the longest substring length at each position and to compute the length at the succeeding position. It's convenient to initialize the prevIndexOf array with zeros, so the index computations have to be offset by one to account for that.


Log in to reply
 

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