Title description:

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

Example 1:

Enter: s = “abcabcbb”

Output: 3

Explanation: Since the oldest string without repeating characters is “ABC”, its length is 3.

Example 2:

Input: s = “BBBBB”

Output: 1.

Explanation: Since the oldest string without repeating characters is “b”, its length is 1.

Example 3:

Enter: 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.

Example 4:

Enter: s = “”

Output: 0

Tip:

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

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

LeetCode link: leetcode-cn.com/problems/lo…

Ideas:

When we look at the problem, we can first grasp the two core requirements

1. Find the longest substring of the incoming string

2. This maximum string has no duplicate characters

We can grasp these two core points to analyze this problem, to solve this problem, we can use the sliding window idea, the sliding window idea can deal with these two core points very well

As the name suggests, a sliding window is a window that slides left and right (queue). We move the window as elements are added or removed from the queue. As in this problem, if we set a string juejin, the queue entry requirement is non-repeating characters. So here first to go in the string of jue, then continue to preach j, because in front of the queue have j, then will be unable to enter, so in order to enter the queue, we will in the queue with the same characters and their characters to delete before, so this time you need to move the window, we will make moves to the right window, By removing the element j on the left and recording the maximum value for each incoming character operation, you can find the longest non-repeating substring in the string by going in and out

Therefore, through the sliding window idea, the problem of no repetition is solved by moving operation, and the problem of maximum number of strings is solved by recording operation

So, let’s take a look at the code

var lengthOfLongestSubstring = function(s) { let arr = new Array(); let max = 0; for(let i=0; i < s.length; i++) { let index = arr.indexOf(s[i]) if(index ! == -1) { arr.splice(0,index + 1) } arr.push(s[i]) max = Math.max(arr.length,max) } return max }Copy the code

Time complexity: O(n)

Practice description

  1. Set up aarrSliding window, used to receive external incoming string, used when incomingindexof()Method, and if there are no duplicate elements, it is loaded
  2. When passed, if the value passed is a repeating element splice()The duplicate character () method cuts off the preceding character and passes in a new charactermaxRecord the queue length
  3. When passed, if the value passed is a non-repeating elementpush()Method queues characters directly and usesmaxRecord the queue length

Thus, after iterating through the string, Max records the length of the longest non-repeating character substring

The last

This is my first article of Leecode, there may be a lot of errors in the semantic description, if you have any questions please point out in the comments section

If you find this article helpful, please give it a thumbs up