This article was originally published in The Language Sparrow Archive

The title

Leetcode-cn.com/problems/lo…

Flowchart & Debug code

All flow charts & debug codes are subject to the Github repository

Github.com/blueju/leet… /

First attempt

code

/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function (s) {
    let stack = new Set(a);for (let i = 0; i < s.length; i++) {
        for (let j = i; j < s.length; j++) {
            if (stack.has(s[j])) {
                stack.clear();
                continue; }}}return stack.length;
};
Copy the code

The flow chart



The results of

Failed test cases are:

  • It is not possible to count the maximum number of non-repeating characters, because every time a duplicate item is found, the stack is cleared directly, which is also a misunderstanding of the question.


Second attempt

code

/ * * *@param {string} s
* @return {number}* /
var lengthOfLongestSubstring = function (s) {
    let resultStack = new Set(a);let tempStack = new Set(a);for (let i = 0; i < s.length; i++) {
        for (let j = i; j < s.length; j++) {
            if (tempStack.has(s[j])) {
                if (tempStack.length > resultStack.length) {
                    resultStack = new Set([...tempStack]);
                    tempStack.clear();
                } else {
                    tempStack.clear();
                }
                break;
            } else{ tempStack.add(s[j]); }}}return resultStack.length;
};
Copy the code

The flow chart

conclusion

Failed test case

Wrong:

  • Error using the Set statistics length API
  • Interrupt escape using for incorrectly


​

Third attempt

code

/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function (s) {
    let result = new Set(a)let stack = new Set(a)const length = s.length
    for (let i = 0; i < length; i++) {
        for (let j = i; j < length; j++) {
            const item = s[j]
            if (stack.has(item)) {
                if (result.size < stack.size) {
                    result = new Set([...stack])
                    stack.clear()
                } else {

                    stack.clear()
                }
                break
            } else {
                stack.add(item)
            }
        }
    }
    return result.size
};
Copy the code

conclusion

Failed test cases are at fault

  • No special cases are considered (when strings are “” and “” and strings are 0 and 1 in length)

​

Think about:

  • The results are always stored in complex data structures, okay? I just need the length.

​

Fourth attempt (by test case)

code

/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function (s) {
    const length = s.length
    if (length === 0) return 0
    if (length === 1) return 1
    let maxLength = 0
    let stack = new Set(a)for (let i = 0; i < length; i++) {
        for (let j = i; j < length; j++) {
            if (stack.has(s[j])) {
                maxLength = Math.max(maxLength, stack.size)
                stack.clear()
                break
            } else {
                stack.add(s[j])
            }
        }
    }
    return maxLength
};
Copy the code

The flow chart

conclusion

The test case passed





​

Fifth attempt (by test case)

If we were abCD and c, then the BCD stored in the previous ABCD would be pushed into the next for loop with index I.

Then, when we judge whether there is the same data as s[j] in the stack, and if there is, we can also judge its position, and then in the next for loop with index I, we can directly locate I to the last digit of the repeat item. For example, when ABcd meets C in the above paragraph, we can directly locate I to D. This saves the time for I to start at b in the next loop.

code

/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function (s) {
    const length = s.length
    if (length === 0) return 0
    if (length === 1) return 1
    let maxLength = 0
    let stack = []
    for (let i = 0; i < length; i++) {
        for (let j = i; j < length; j++) {
            const index = stack.indexOf(s[j])
            if (index > -1) {
                maxLength = Math.max(maxLength, stack.length)
                stack.length = 0
                i = i + index
                break
            } else {
                stack.push(s[j])
                maxLength = Math.max(maxLength, stack.length)
            }
        }
    }
    return maxLength
};
Copy the code

The flow chart

conclusion

The test case passed

Although the execution time was actually longer than the 4th attempt, I think the main reason was the change of Set to Array, and I also tried to change the 4th attempt to Array, which also extended the execution time to 600+ ms. But even that is not much faster, and it is reasonable to suspect that the length of test cases is not long enough.



Think about:

  • Can we just do it in one for loop

​

Sixth attempt (by test case)

We used to change the index of the first layer for loop every time we found a duplicate item. We used abcdb again. The first time we found a duplicate item b, the stack value was abcd; If the test case is longer, then the repeated items such as CD will also be longer. Should we consider caching them?

It seems that examples are important to see patterns.

code

Based on the fourth attempt, we can change it to the following:

/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function (s) {
    const length = s.length
    if (length === 0) return 0
    if (length === 1) return 1
    let maxLength = 0
    let stack = []
    for (let i = 0; i < length; i++) {
        if (stack.includes(s[i])) {
            stack.shift()
            i--
        } else {
            stack.push(s[i])
            maxLength = Math.max(stack.length, maxLength)
        }
    }
    return maxLength
};
Copy the code

Based on the fifth attempt, we can change it to the following:

/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function (s) {
    const length = s.length
    if (length === 0) return 0
    if (length === 1) return 1
    let maxLength = 0
    let stack = []
    for (let i = 0; i < length; i++) {
        const result = stack.indexOf(s[i])
        if (result > -1) {
            stack.splice(0, result + 1)
            i--
        } else {
            stack.push(s[i])
            maxLength = Math.max(stack.length, maxLength)
        }
    }
    return maxLength
};
Copy the code

The results of

Much faster than before