This is the 15th day of my participation in the More text Challenge. For more details, see more text Challenge

Maximum string with no duplicate characters (Question number 3)

The title

Given a string, find the longest 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 duplicate characters is "b", its length is 1.Copy the code

Example 3:

Input: s = "pwwkew" Output: 3 Explanation: Since the oldest string with no duplicate 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

link

Leetcode-cn.com/problems/lo…

explain

This one. This one is a punch.

I have such a feeling that the medium questions in the front of Leetcode seem very simple. I don’t know why.

As soon as I saw this problem, I thought of two solutions:

  1. Violent solution

    Violence. It’s easy. It’s done.

    Let’s start with an object or a Map and start looping. Then we store I as the key in this object, and every time we get to a new element, we check if that element exists in every array in the object, and if it doesn’t, we insert the current element into the array, and if it does, we skip it.

    But you can do some pruning as you go through the loop, and you can tell by the length of the array whether the array is broken, that it’s not possible to insert elements, or you can skip that array, and you don’t have to tell if it exists, because you want the substring to be continuous.

    We get an object, we loop through every element in the object, we take the length of the array and compare it to Max.

  2. Dynamic programming (questionable)

    The question here is not whether the solution is correct, but whether the method is dynamic programming.

    Method is very simple, first, a new array, after each cycle when the judge whether there is this element in the array, if there is no direct insertion, and Max is compared, if there is to remove the beginning of the element, to determine if there is, will continue to get rid of the beginning of the element, for a traversal operation, until the element does not exist, then insert the new element.

    That’s it.

    Why DP? Because the longest string in each new position is related to the longest string in the previous position, so the value in the array is always the longest string in the current position, kind of like dynamic programming, but it’s probably just memorized, which is debatable, but you can point that out in the comments section if you’re clear.

Your own answer (violence -> Object)

The logic is simple. Just pay attention to pruning.

var lengthOfLongestSubstring = function(s) { var map = new Map() max = 0 for (let i = 0; i < s.length; i++) { for (let j = 0; j < i; j++) { var res = map.get(j) if (res && res.length > i - 1 - j && ! res.includes(s[i])) { map.set(j, [...res, s[i]]) } } map.set(i, [s[i]]) } for (const item of map.values()) { max = Math.max(item.length, max) } return max };Copy the code

The logic is explained in the explanation section, but this is just the implementation.

The only fly in the ointment is that there is no AC. When it comes to 986 use cases, GG is the second to last, but it still fails.

Your own answer (Dynamic Programming -> Array)

var lengthOfLongestSubstring = function(s) {
  var arr = []
      max = 0
  for (const chat of s) {
    while (arr.includes(chat)) {
      arr.shift()
    }
    arr.push(chat)
    max = Math.max(arr.length, max)
  }
  return max
};
Copy the code

The amount of code is much less, and the logic is simple.

This solution feels like a loophole, because the problem requires it to be a substring, and the implication is that it must be continuous, so as long as you keep removing the beginning element, you’re done without any difficulty.

Better method (Sliding window -> doubt)

In fact, I feel that the solution of sliding window should not be put in a better method, because it is not as efficient as the previous solution of dynamic programming. The time and space of dynamic programming are more than 90%, but this solution can only hover around 60%~70%.

The main logic of sliding Windows is similar to that of dynamic programming, but there is a slight difference.

The official explanation is more complicated, here is a simple translation.

First of all, the array must begin with the current element, and the array must begin with the current element.

And then we take a right pointer, and we iterate from zero.

Insert elements into the array during iteration, and then increment the right pointer by 1. When will it stop? There are two conditions:

  1. The right pointer runs out, which, needless to say, is the natural case to stop iterating.
  2. We already have an element in the array where the right pointer is located, so we stop iterating.

We can use the element at the beginning of the array as the left pointer, because we remove the first element of the array each time we start the loop, so we keep the left pointer at the current point in the loop.

In this way, the interval between the left and right Pointers is a window. By changing the position of the left and right Pointers to slide the window, it becomes a sliding window.

👇 look at the code (I wrote it myself, and the official is a little different).

var lengthOfLongestSubstring = function(s) { var set = new Set() max = 0 right = 0 len = s.length for (let i = 0; i < len; i++) { if (i ! == 0) { set.delete(s.charAt(i - 1)) } while (right < len && ! set.has(s.charAt(right))) { set.add(s.charAt(right)) right++ } max = Math.max(max, right - i) } return max };Copy the code

What’s the difference? Is the initial position of the right pointer, the official initial position of the answer is -1, but I tried, it is ok to start from 0, so I don’t understand, why start from -1? Anyone who knows is welcome to leave a message in the comment area or send a personal message to the author. Thank you very much.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ