Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

Hello everyone, I am quick-frozen fish 🐟, a front end of water system 💦, like colorful whistle 💐, continuous sand sculpture 🌲, I am a good brother of the next door Cold grass Whale, I just started to write an article. If you like my article, you can follow ➕ to like it, inject energy into me, and grow with me

The title 🦀

• 3. The oldest string without repeating characters

  The difficulty of medium

  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

  Example 2:

  Input: s = "BBBBB" Output: 1 Explanation: Since the oldest string without repeating characters is "b", its length is 1.Copy the code

  Example 3:

  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

  Example 4:

  Input: s = "output: 0Copy the code

  Tip:

  • 0 <= s.length <= 5 * 104

  • S consists of letters, digits, symbols, and Spaces

🌵

• Start by finding all substrings that do not contain repeating characters

• Find the substring with the largest length and return its length

• Maintains a sliding window with double Pointers for clipping substrings.

• Keep moving the right pointer to duplicate characters and move the left pointer to duplicate characters

Source 🔥

/ * * *@param {string} s
 * @return {number}* /
var lengthOfLongestSubstring = function(s) {
  // Initialize the left pointer
    let l=0;
  // Initialize the right pointer
    let res=0;
  // This map is used to store duplicate characters
    const map=new Map(a)// Iterate over the character, sliding the right pointer
    for (let r=0; r<s.length; r++){// If a duplicate character is encountered, and the duplicate character is in the sliding window, move the left pointer
      if(map.has(s[r])&&map.get(s[r])>=l){
            l=map.get(s[r])+1;
        }
      // Save the maximum value
        res=Math.max(res,r-l+1);
        map.set(s[r],r);
    }
    return res;
};
Copy the code

Time complexity :O(n)

Space complexity :O(m), where M is the number of non-repeating characters in a string

Conclusion 🌞

So the Leetcode03- the maximal string without repeated characters in The LeetCode algorithm chapter of Yu Yu is over. There is no shortcut for algorithm, so we can only write and practice more and summarize more. The purpose of this article is actually very simple, which is to urge myself to complete algorithm practice and summarize and output. I hope everyone can like my essay, and I also hope to know more like-minded friends through the article. If you also like to toss, welcome to add my friend, sand sculpture together, together progress.

Making 🤖 : sudongyu

Personal blog 👨💻: Frozen fish blog

Vx 👦 : sudongyuer

Write in the last

Guys, if you like my words, give 🐟🐟 a thumbs up 👍 or follow ➕ to support me the most.