Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Title Description:

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

The sample

Enter: s ="abcabcbb"Output:3Because the oldest string without repeating characters is"abc", so its length is3. The sample2: Enter: s ="bbbbb"Output:1Because the oldest string without repeating characters is"b", so its length is1. The sample3: Enter: s ="pwwkew"Output:3Because the oldest string without repeating characters is"wke", so its length is3. Please note that your answer must be the length of the substring,"pwke"It's a subsequence, not a substring.Copy the code

Tip:

  • 0 <= s.length <= 5 * 104
  • sThe name consists of letters, digits, symbols, and Spaces

Ii. Solution:

Method 1 array interception

  • Principle. Use an array record to determine the maximum array length.
  • Train of thought.
    • Traversal string
    • If the recorded array contains the string, the longest array length is recorded first. It then intercepts the array elements before the occurrence of the string
    • Continue to put the non-repeating string into the array

Code:

var lengthOfLongestSubstring = function(s) {
    let arr = []
    let max = 0
    for(let i of s){
        if(arr.includes(i)){
            max = Math.max(max, arr.length)
            arr.splice(0, arr.findIndex(it= > it === i)+1)
        }
        arr.push(i)
    }
    return Math.max(max, arr.length)
};
Copy the code

Method 2 Map position recording method

  • Principle. Use Map to record the character position and the start of the character to calculate the maximum length.
  • Train of thought.
    • Traversal string
    • If the string exists in the map
    • Change the start position based on map.get(s[I]) and the start size
    • Sets or resets s[I] to the current position of the next value
    • Get the maximum by comparison

Code:

var lengthOfLongestSubstring = function(s) {
    let map = new Map(a)let max = 0
    let start = 0
    let n = s.length
    for(let i = 0; i < n; i++){
        if(map.has(s[i])){
            start = Math.max(map.get(s[i]), start)
        }
        map.set(s[i], i + 1)
        max = Math.max(max, i + 1 - start)
    }
    return max
};
Copy the code

Third, summary

  • This problem can be Set to double method and double pointer traversal method of two schemes
  • Array interception method mainly uses array record not repeating characters, judge the longest array length can be.
  • Map position recording method mainly uses Map to record the character position and the beginning position of the character to calculate the maximum length.

If there are any errors in this article, please correct them in the comments section