Title: Algorithm (leetode, with mind map + all solutions) 300 questions (3) the most eldest string without repeated characters

A Description of the topic

Overview of Two Solutions (Mind Mapping)

Three complete solutions

Scheme 1

1) code:

var lengthOfLongestSubstring = function(s) {
    // Determine whether each character in the current "substring" is unique
    const checkSubStrCharUnique = (subStr) = > {
        // Tip: Hash (Map in JS) data structures are preferred when dealing with "uniqueness" and "quantity"
        let map = new Map(),
            l = subStr.length,
            flag = true;

        for (let i = 0; i < l; i++) {
            // If the character has been stored in map before, return false
            if (map.has(subStr[i])) {
                flag = false;
                break;
            } else {
                // The second parameter in set is meaningless
                map.set(subStr[i], 1); }}return flag;
    }


    let resLength = 0,
        l = s.length;
    
    // Slide window length range [L, 1]. ResLength = 0; resLength = 0;
    // curLength -- the length of the sliding window for this loop
    for(let curLength = l; curLength >0; curLength--) {
        // start -- start the subStr of this loop
        for (let start=0; start<=l-curLength; start++) {
            // The length of the loop's sliding window + subStr starting subStr --> subStr
            // And determine if subStr is "valid". If yes, curLength of the current sliding window is the expected answer!
            const subStr = s.substr(start, curLength);
            if (checkSubStrCharUnique(subStr)) {
                resLength = curLength;
                returnresLength; }}}return resLength;
}
Copy the code

Scheme 2

1) code:

// Option 2 -- Optimized "Violent Sliding window"
var lengthOfLongestSubstring = function(s) {
    let i = 0,
        l = s.length,
        // Record the current no repeated character substring
        curUniqueArr = [],
        // The maximum length of the current non-repeating character substring
        resLength = 0;
    
    while(i < l) {
        CurUniqueArr = curUniqueArr = curUniqueArr
        if(curUniqueArr.indexOf(s[i]) === -1) {
            curUniqueArr.push(s[i]);
            // Determine whether the current resLength needs to be updated
            resLength = Math.max(resLength, curUniqueArr.length);
        } else {
            // Delete the first character of curUniqueArr
            // Then continue -- determine if the first character of curUniqueArr needs to be removed again!
            // Example: s = "pwwkew" (" PWW "need to remove p, w)
            curUniqueArr.shift();
            continue;
        }
        i++;
    }

    return resLength;
};
Copy the code

3 solution 3

1) code:

// Option 3 -- An optimized version of "Violent Sliding Windows". It's actually an optimized version of Plan 2,
// I = map.get(s[J]); Instead of "discard the first character of curUniqueArr until curUniqueArr no longer contains s[I]" in scheme 2
var lengthOfLongestSubstring = function(s) {
    let l = s.length,
        resLength = 0.// For "uniqueness" and "quantity", the Map data type is preferred
        map = new Map(a);-- I = map.get(s[J]);
    for(let i=0; i<l; i++){
        let j = i;
        map.clear();
        while(j < l){
            // Insert s into map [j]
            if(! map.has(s[j])){// Select * from s[j] where s[j] = s[j];
                map.set(s[j], j);
            }else{
                // Repeat, update resLength
                resLength = Math.max(resLength, map.size);
                // Need to jump to the next element subscript that repeats the current s[j] character -- +1,
                Get (s[j]) -- +1
                i = map.get(s[j]);
                break;
            }
            j++;
        }
        // Some situations come to an end.
        resLength = Math.max(resLength, map.size);
    }

    return resLength;
}
Copy the code