【LeetCode】 The largest string without repeating characters (medium) – Set – slide window – Shrink window

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Today we look at a string related problem, here using JavaScript to give three solutions, the third one is the most simple solution I think of, I also give a detailed parsing process, you can see ~

3. The oldest string without repeating characters

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

Power button address

【 典 型 例 句 1 】 Violent traversal + Set

The first thing that comes to mind is a violent traversal, which starts with each string and traverses it twice

function lengthOfLongestSubstring(s) {
  let len = s.length;
  let result = 0;

  for (let i = 0; i < len; i++) {
    let set = new Set(a);let maxLen = 0;
    // Get the length of the longest string from the position of I
    let j = i;
    while(j < len && ! set.has(s[j])) { set.add(s[j]); maxLen++; j++; }// Take the historical maximum
    result = Math.max(result, maxLen);
  }
  return result;
}
Copy the code

【 solution 2 】 Sliding window

This is the official answer to the question, which is not particularly clear, see the notes for details

function lengthOfLongestSubstring(s) {
  let len = s.length;
  let result = 0;
  let set = new Set(a);// The right pointer, starting with -1, means we are to the left of the string's left boundary and have not started moving
  let j = -1;
  
  for (let i = 0; i < len; i++) {
    if(i ! = =0) {
      // The left pointer moves one space to the right to remove a character
      set.delete(s[i - 1]);
    }
    while (j + 1< len && ! set.has(s[j +1]) {// Keep moving the right pointer
      set.add(s[j + 1]);
      j++;
    }
    // The i-jth character is an extremely long non-repeating character substring
    result = Math.max(result, j - i + 1);
  }
  return result;
}
Copy the code

【 solution 3 】 Double pointer – sliding (shrinking) window

And you can actually optimize it by looking at it, so let’s make a window, let’s make a window that has a string that satisfies the problem. How do we make it satisfy the problem? To do that, slide the window, looping to remove the first element on the left until there are no duplicate elements in the window, then expand the window

Sliding Windows have two key points: expansion + contraction

• First (right pointer) expand to the sliding window does not meet the conditions of the pause,

• (left pointer) Start to shrink the window until it meets the condition and then expand it (right pointer)

function lengthOfLongestSubstring(s) {
  let len = s.length;
  let result = 0;

  let set = new Set(a);// The left pointer is used to shrink the window
  let left = 0;
  // The right pointer is used to expand the window
  let right = 0;

  while (left < len) {
    // If not, expand the window and add elements to the set
    while(right < len && ! set.has(s[right])) { set.add(s[right]); right++; }< span style = "box-sizing: border-box; color: RGB (74, 74, 74); line-height: 22px; font-size: 14px! Important; word-break: inherit! Important;
    result = Math.max(result, right - left);
    // Shrink the window
    set.delete(s[left]);
    left++;
  }
  return result;
}
Copy the code