My O(n) solution , runtime: 5ms


  • 18
    int lengthOfLongestSubstring(char *s) {
        int m[129] = {0};
        int i, j;
        int cnt = 0, pre = 0;
        int max = 0;
        int c;
    
        for (i = 0; c = s[i]; i++) {
            if (pre < m[c]) {
                if (max < cnt)
                    max = cnt;
    
                cnt = i-m[c];
                pre = m[c];
            }
    
            cnt++;
            m[c] = i+1;
        }
        return max > cnt ? max : cnt;
    }

  • 0
    W

    can you explain why?


  • 8
    G

    I like the idea pre < m[c], so that the map don't have to be cleared out when we move pre forward.
    But I am surprised that test cases only cover basic ASCII characters. Normally in this kind of problems we will be asked to handle Unicode. I don't know much about C, it seems that char *s is not enough to handle Unicode.


  • 0
    S

    You don't have to use cnt++


  • 0
    H

    Great advice! And could you show the code or basic idea of handling Unicode text? I have no such expericece before : )


  • 0
    I

    why use 128?


  • 0
    S

    why use 128? because there are 128 valid ASCII characters (though the range of char is from 0x00 to 0xFF).


  • 0
    I

    got it! thanks for answering


  • 0
    T

    If there are 128 "valid" ASCII characters, why use 129 as size? That gives 0..128 as indices... which is one more than needed.


Log in to reply
 

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