How to find non-repeating substrings in JavaScript

In actual development, we often need to perform some operations and processing on strings, one of which is to find non-repeating substrings. For example, in the string "abcabcbb", the longest non-repeating substring is "abc", and in the string "bbbbbb", the longest non-repeating substring is "b". These problems are known in algorithms as the "longest non-repeating substring" problem, and we can solve them using JavaScript.

1. Violent enumeration method

The simplest method is to use brute force enumeration method, that is, traverse the string from scratch for each character and add non-repeating characters one by one. substring until repeated characters are encountered. Then, record the length of the substring at this time, reset the substring, and continue traversing the string downward until the end of the traversal.

The code is as follows:

function longestSubstring(str) {
  let maxLength = 0; // 定义最大长度为 0
  for(let i = 0; i < str.length; i++) {
    let map = new Map(); // 定义 Map 来保存子串中元素出现的次数
    let length = 0; // 定义子串长度为 0
    for(let j = i; j < str.length; j++) {
      if(map.has(str[j])) { // 如果子串中已经有这个元素了
        maxLength = Math.max(maxLength, length); // 更新最大长度
        break; // 说明这个子串已经不符合要求了，跳出内部循环
      } else {
        map.set(str[j], 1); // 在 Map 中记录该元素的出现次数
        length++; // 子串长度 +1
        maxLength = Math.max(maxLength, length); // 更新最大长度
      }
    }
  }
  return maxLength;
}

The time complexity of this method is O(n^3). Since the number of nested loops is very large, it is not efficient when processing longer strings. Very low.

2. Sliding window method

In order to improve efficiency, we can use the sliding window method. The idea of ​​sliding window is to maintain a window of length k and slide this window to process strings. In this problem, the length of the sliding window is the length of the non-repeating string.

Specifically, when traversing a string, we define a starting pointer and an endpointer, and these two pointers will form a window. In each loop, if the element pointed to by the end pointer does not exist in the window, we can add it to the window, then expand the window and update the length of the window. If the element pointed to by the end pointer already exists in the window, we need to move the start pointer to the right and shrink the window until the element pointed to by the end pointer no longer exists in the window. In this process, we need to use a mapping table to record the number of occurrences of each element in the window.

The code is as follows:

function longestSubstring(str) {
  let maxLength = 0; // 定义最大长度为 0
  let map = new Map(); // 定义 Map 来保存元素出现的次数
  let left = 0; // 定义左指针为 0
  for(let right = 0; right < str.length; right++) {
    if(map.has(str[right])) { // 如果窗口内已经有该元素了
      left = Math.max(left, map.get(str[right]) + 1); // 更新左指针，向右移动
    }
    map.set(str[right], right); // 在 Map 中记录该元素的位置
    maxLength = Math.max(maxLength, right - left + 1); // 更新最大长度
  }
  return maxLength;
}

The time complexity of the sliding window method is O(n). It uses HashMap to quickly locate and store characters. It is faster and more efficient than the brute force enumeration method.

3. Summary

For the problem of the longest non-repeating substring in a string, we can use two methods to solve it: brute force enumeration method and sliding window method. The brute force enumeration method has a high time complexity, while the sliding window method is more efficient. In actual development, we can choose the appropriate method to solve the problem as needed.

The above is the detailed content of How to find non-repeating substrings in JavaScript. For more information, please follow other related articles on the PHP Chinese website!