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:

One day I went to Tencent for an interview, and he gave me an algorithm problem, which I had not written at that time. The topic seemed to be providing a string, and I needed to find the maximum string length without repetition in the string. The topic also did not have much useful information, brain buzzing do not know how to start.

Ii. Analysis of Ideas:

The input parameter is a string and the output is the length of a substring. Assuming that the supplied string is “abcc”, let’s list all possible substrings:

We can think of it as 3 intervals

Interval 1 AB ABC ABCC interval 2 BC BCC interval 3 ccCopy the code

So write the following code:

function lengthOfLongestSubstring (s) {
  let len = s.length
  if (len <= 1) return len
  let maxLen = 1
  for (let i = 0; i < len; i++) {
    for (let j = i + 1; j < len; j++) {
      if (allUnique(s, i, j)) {
        maxLen = Math.max(maxLen, j - i + 1)}}}return maxLen
}
function allUnique(s, start, end) {
  let set = new Set(a)for (let i = start; i <= end; i++) {
    if (set.has(s[i])) {
      return false
    }
    set.add(s[i])
  }
  return true
}

console.log(todo('abcc'))
Copy the code

Violent solution: run through all the intervals of the number group, and find the longest interval without repeating characters, time complexity: O(n^3).

Check all substrings one by one to see if they have any unique characters. Substrings can be generated using a double loop, the first iterating over the start character of the substring and the second iterating over the end character of the substring. Iterate over each substring to see if it has any more unique characters.

Because of the high complexity of the violent solution, you need O(n^2) to generate the substring, and then you need to look for repeated characters to find the oldest string, O(n), and O(n^3) in general.

Now, the right way to do this is to use a sliding window, so let’s not explain what a sliding window is, but let’s look at the code.

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

In the introduction of sliding window frame, we first from the literal understanding:

  • Slide: indicates that the window is moving, that is, the movement is in a certain direction.
  • Window: the window size is not fixed, can be continuously expanded until certain conditions are met;

From the code, we slide from zero position, and then expanding window until you find the set of heavy exists repetitive characters when stop, this time the size of the window is 3 contains characters of ABC, and then began to slide to the position of 1, note before you start to delete a, then window kept the BC, expanding the scope of the window after from c.

Note: the sliding position is moved backwards, but the size of the window is not fixed. Previously calculated Windows can be saved for next use.

Iv. Summary:

In fact, this problem is quite difficult, using a sliding window to order N time. If you understand the sliding window protocol, you’ll probably get a better idea.

Those of you who have studied computer networks know the Sliding Window Protocol, which is an application of TCP. It is used for traffic control during network data transmission to avoid congestion. This protocol allows the sender to send multiple packets of data before stopping and waiting for confirmation. Because the sender does not have to stop for confirmation every time a packet is sent. Therefore, the protocol can speed up data transmission and improve network throughput.