Shortest O(n) DP solution with explanations


  • 115
    D
    /**
     * Solution (DP, O(n)):
     * 
     * Assume L[i] = s[m...i], denotes the longest substring without repeating
     * characters that ends up at s[i], and we keep a hashmap for every
     * characters between m ... i, while storing <character, index> in the
     * hashmap.
     * We know that each character will appear only once.
     * Then to find s[i+1]:
     * 1) if s[i+1] does not appear in hashmap
     *    we can just add s[i+1] to hash map. and L[i+1] = s[m...i+1]
     * 2) if s[i+1] exists in hashmap, and the hashmap value (the index) is k
     *    let m = max(m, k), then L[i+1] = s[m...i+1], we also need to update
     *    entry in hashmap to mark the latest occurency of s[i+1].
     * 
     * Since we scan the string for only once, and the 'm' will also move from
     * beginning to end for at most once. Overall complexity is O(n).
     *
     * If characters are all in ASCII, we could use array to mimic hashmap.
     */
    
    int lengthOfLongestSubstring(string s) {
        // for ASCII char sequence, use this as a hashmap
        vector<int> charIndex(256, -1);
        int longest = 0, m = 0;
    
        for (int i = 0; i < s.length(); i++) {
            m = max(charIndex[s[i]] + 1, m);    // automatically takes care of -1 case
            charIndex[s[i]] = i;
            longest = max(longest, i - m + 1);
        }
    
        return longest;
    }
    

    Hope you like it :)


  • 6
    G

    My idea is pretty much the same with yours, only with a few subtle details:

    1. I don't use vector or other objects to implement the mapping between idx and ASCII value. In fact, all you need is an integer array, and all will be fine.
    2. An array of size of 128 will do the job.

    Great work though :)


  • 0
    N

    agree with you


  • 0
    N

    nice idea! concise and pretty


  • 0
    E

    why it is 128? char has 8 bit ,so i guess it will need 256?


  • 0
    C

    so pretty!!!


  • 1
    A

    Great idea!!!!!!!


  • 0

    Well, personally I guess that the last 128 characters in the ASCII table are hard to be printed out and so the test cases do not contain those characters. Thus, an array of size 128 will do the job.


  • 0

    Damn clever idea!!! Absolutely brilliant!


  • 2
    C

    in your comment, 2) if s[i+1] exists in hashmap, and the hashmap value (the index) is k

    • let m = max(m, k), then L[i+1] = s[m...i+1], we also need to update
    • entry in hashmap to mark the latest occurency of s[i+1].

    maybe it should be let m = max(m, k+1), tell me if i am wrong


  • 4
    H

    Great, but i think if you use "start" or "begin" instaed of "m",it will be more easy to unsatnd.


  • 0
    S

    neat hack!!!!!


  • 0
    H

    Fantastic!!!!


  • 0
    T

    They're not that hard to print, here're some characters we use every day from 128-255: áéóöőúüű (assuming ISO-8859-2 extended ASCII character encoding)


  • 2

    I do think your solution has no relation-ship with DP , your answer is almost the same as the top voted answer. 233333


  • 5

    Why is this DP????


  • 0
    H

    What's the space complexity of this solution? O(1)?


  • 3
    E

    It works, but where is the dp?


  • 0

    @Eddie-wang Do you know string?

    string is defined as below:

    typedef basic_string<char> string;
    

    so, 128 is enough to cover all the right chars!


  • 0
    X

    @dragonmigo good idea~


Log in to reply
 

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