preface

Dangdang, I don’t have a title party oh, this is the author of the recent interview bytefly book front-end development position encountered a real interview question, in line with the concept of joy alone is better than all joy, let us take it as a breakthrough point, start our string exploration journey.

Keywords: hand-torn code, string method, string correlation algorithm

Subject overview

Given a string s, find the length of the smallest string that does not contain repeating characters.

Example 1: Input: s = "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3.Copy the code
Input: s = "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1.Copy the code
Input: s = "pwwkew" Output: 3 Explanation: Since the oldest string without repeating characters is "wKE", its length is 3. Note that your answer must be the length of the substring, "pwke" is a subsequence, not a substring.Copy the code

🤔

First, we need to be clear about the concept of a nonrepeating string: a contiguous substring containing no repeating characters within a given string,

The second thing we need to be careful about is whether we’re returning a length or a specific substring, but notice that we’re only returning the length of the substring.

As you can imagine, iterating through the string is a must, and the key is to determine where the resulting substring starts and ends.

The answer

PS: If you don’t want to announce the puzzle so quickly, you can try it yourself first. Here are two solutions and code annotations based on the data and your own understanding.

Solution 1 Sliding window (Tc O(n) Sc O(1))

The sliding window concept is common in linear structure data structures, including the core of TCP control reliability. The sliding window concept is also the core of TCP control reliability

var lengthOfLongestSubstring = function(s) {
    // Initialize empty STR as our sliding window
    let str = ' '; 
    // The default maximum non-repeating substring length is 0
    let length = 0;
    for (let i = 0; i < s.length; i++) {
       if (str.indexOf(s[i]) == -1) {
           // If the current window does not contain s[I], append s[I] to the end of STR string.
           str += s[i]
       } else {
           // If the current window contains s[I], take the maximum value between the sliding window length and the previously recorded length
           / /! Notice that you take the big value and then you slide it
           length = Math.max(str.length,length);
           // Truncate the STR header to the first position equal to the value of s[I], append s[I] to the end of STR string, implement window sliding
           str = str.slice(str.indexOf(s[i]) + 1) + s[i]; }}// Finally, remember to maximise the length of the sliding window and the length of the previous record
    return  Math.max(length, str.length);
};
Copy the code

Solution 2 The triple loop of violent solution (Tc O(n^3) Sc O(1))

The violent solution is the last guarantee option when there is no other better idea. It can be seen that the test result of the violent solution is not very ideal, but the idea of solving the problem (Mianshi) is far better than no idea, so you can also look at the idea of the violent solution to make a base.

var lengthOfLongestSubstring = function (s) {
    // If a string length of 0 is passed in, 0 is returned.
    if (s.length < 1) {   
        return 0;
    }
    // Initialize the maximum string length to 1;
    let max = 1;   
    // Every time the substring starts right, set the substring length to 1; It's just that every time the starting position changes, the substring becomes a new substring.
    for (let i = 0; i < s.length; i++) {
        let curLength = 1;   
        // the j pointer is used to control the last substring subindex
        for (let j = i + 1; j < s.length; j++) {   
             // diff is used to identify whether the current substring is different for each character
            let diff = 1;  
            // Compare the last character of the substring with all the characters in the substring
            for (let k = i; k < j; k++) {      
                if (s[j] === s[k]) {
                    diff = 0; }}if (diff) {
                // If both are different, the current substring length counts variable increment by one
                curLength++; 
                // Save the maximum number of string digits
                max = Math.max(max,curLength);
            } else {
                break; }}}return max;
};
Copy the code

Analysis of string related methods

Personally, I prefer mind mapping and table. Here I use mind mapping to sort out the string related methods.

References:

CUGGZ JavaScript 28 common string methods and use skills (recommended, my mind map is to see the blogger’s article plus their own learning and use habits of sorting out the second)

FE good friend MDN (recommended, in addition to the use of methods but also introduced the browser on various types of JS object method compatibility and method ECMAJS support version)

Analysis of string correlation algorithms

Here with mind map to the string often test related algorithms also do a collation, convenient review.

References (Recommended reading) :

Loadings front-end data structure and algorithm summary of high-frequency questions (recommended, my mind map is based on the blogger’s article and my own interview and brush questions record)

FE’s other good friend LeetCode

To be continued

In sorting out their own sliding window related understanding, will be divided into principle, implementation, application to talk about, I hope I can fill the hole as soon as possible ~! At the same time, I am also sorting out all kinds of interview and written test questions I have met recently (there is still a lot to learn and understand, come on).

I hope this article helped you as much as it helped me, and I’ll see you soon 👋🏻