For longest substring w/o repeating chars question, why my O(n) javascript solution only beats 55%?


  • 0
    R

    here's my solution:

    var lengthOfLongestSubstring = function(s) {
        if (s.length === 0) { return 0; }
        var start = 0, maxLen = 1, dict = {};
        for (var j = 0; j < s.length; j++) {
            var c = s.charAt(j);
            // found a repeating char
            if (dict.hasOwnProperty(c) && dict[c] >= start) {
                start = dict[c]+1;
            }
            
            dict[c] = j;
            var currLen = j-start+1;
            if (currLen > maxLen) {
                maxLen = currLen;
            }
        }
        return maxLen;
    };
    

    what's better solution?

    with @nsky's suggestion, changing to use methods of String object instead of hashmap, it does perform better, it now beats 96%.

    var lengthOfLongestSubstring = function(s) {
        if (s.length === 0) { return 0; }
        var start = 0, maxLen = 1;
        // var dict = {};
        for (var j = 0; j < s.length; j++) {
            var c = s.charAt(j);
            // found a repeating char
            // if (dict.hasOwnProperty(c) && dict[c] >= start) {
            //     start = dict[c]+1;
            // }
            var idx = s.substring(start, j).lastIndexOf(c);
            if (idx > -1) {
                start = start + idx + 1;
            }
            
            // dict[c] = j;
            var currLen = j-start+1;
            if (currLen > maxLen) {
                maxLen = currLen;
            }
        }
        return maxLen;
    };

  • 1
    N

    There is nothing wrong with your algorithm, there are some improvements of course but this won't let you beat most of the solutions until you switch to language/platform specific logic.

    My not optimized O(n) Python solution which is 93% faster than others translated to JavaScript is just a little bit faster than yours 56%, there I also use hash maps (Object Literals/Dictionaries).

    But then I rewritten it in JavaScript using String.prototype method(s), and no hash maps, only vars and was able to get faster than 97.73% other solutions result.

    The algorithm of the new JavaScript solution is a little different due to implementation, but it's the same O(n) algorithm. So the answer is in using platform specific logic.


  • 0
    R

    thanks for answering :)


Log in to reply
 

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