preface

Question 3 of LeetCode, “the oldest string without repeating characters”, was an algorithm problem I encountered in the interview process. Through this problem, we can learn a relatively common algorithm to solve the problem: sliding window algorithm.

Since many problems in LeetCode are based on the “sliding window algorithm”, this article will focus on the “sliding window”, not just the algorithm problem. All of these problems can be easily solved once you understand the basic principles of sliding Windows.

Now let’s look at the specific problems and how to solve them.

“Longest string without repeating characters”

Title link: leetcode-cn.com/problems/lo…

Title description:

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

Example:

Input: s = "abcabcbb" Output: 3 Explanation: Since the oldest string without repeating characters is "ABC", its length is 3.Copy the code

The title suggests

The problem is simply to find the length of the smallest string in a string that does not contain repeated characters.

If the problem is cyclically judged by the method of violent profit cracking, the time complexity is directly changed to O(n^2), which is quite scary. Therefore, the sliding window method can be adopted to reduce the time complexity.

What is a sliding window?

The sliding window algorithm operates on a string or array of a particular size, rather than the entire string or array, which reduces the complexity of the problem and thus the nesting depth of the loop. Sliding Windows are mainly used in array and string scenarios.

A simple example

For example, if you have an array [1,3,5,6,2,2] and set the size of the sliding window to 3, then when the window slides from the beginning of the array to the end, calculate the sum of the three elements in each window, denoting sum.

As we can see in the figure above, as the window moves to the right in the array, the data in the window is constantly changing, so we only need to process the data in the continuous interval in the window. Since the interval is continuous, only the data of the old window is clipped when the window moves, which reduces the repeated calculation and time complexity.

For example, when the window is in [1,3,5], after processing the data of the window, move the window to the right by one space, which is equivalent to cutting out the 1 on the left of the original window and adding the 6 on the right of the window, and the whole process looks like the window is moving to the right.

This method can be used to solve problems such as “please find xx of the most x interval (substring, subarray) satisfying XX”.

Basic steps for sliding Windows

Note that: the window movement is in the order of movement; The size of a window is not necessarily fixed and can be continuously reduced or increased.

For the basic solution of the sliding window algorithm, the string S is used as an example as follows:

  • (1) use double pointer to specify the scope of the window, initialize left=right=0, and index closed interval [left,right] is a window.
  • (2) Keep enlarging the window’s right pointer until the string in the window meets the condition.
  • (3) At this point, stop adding right and keep adding left pointer to narrow the window [left,right] until the string in the window no longer meets the requirements. Each time you add a left, you need to update the result of a round.
  • (4) Repeat steps 2 and 3 until right reaches the end of the string.

Among them, the second step is equivalent to looking for a “feasible solution”, and the third step is to optimize the “feasible solution”, and finally find the optimal solution. The left and right Pointers rotate forward, the window size increases and decreases, and the window keeps sliding to the right.

The problem solving

Now that we have learned window-sliding, we are back to LeetCode’s title, which is to change the fixed window of the above example to a varied-size window, and to change the summation to determine whether or not the specified character is included.

Therefore, apply the above ideas for analysis. Using the string “DVDF” as an example, the following figure illustrates the sliding process.

In the above process, it can be decomposed into the following steps:

  • (1) Select the initial value left=right=0, i.e. Window [0,0].
  • (2) Judge whether the character on the right already exists in the window;
  • (3) if the character v is not found in the window, it can be moved right and right one bit, and the window becomes [0,1];
  • (4) Continue to expand the right boundary, right=2, find that D already exists in the window, then stop moving right;
  • (5) At this time, the length of the window is the length of the substring opened with D. Compare the current window length with the historical Max (default value 0) size and find that 2>0, so update Max to 2.
  • (6) start to move left, the window becomes [1,1];
  • (7) continue to expand the right boundary and find that d does not exist in the window, and the window becomes [1,2].
  • (8) continue to expand the right boundary, it is found that f does not exist in the window, and the window becomes [1,3].
  • (9) The maximum length of the string is reached, and the right shift stops. At this time, the current window length and the historical Max size are compared, and it is found that 3>2, so the Max is updated to 3.
  • The length of the longest string that does not contain repeating characters is 3.

With that in mind, let’s look at the Java code implementation of the original problem:

class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int k = 0, max = 0; Set<Character> set = new HashSet<>(); for(int i=0; i< n; i++){ if(i ! = 0){ set.remove(s.charAt(i-1)); } while(k < n && ! set.contains(s.charAt(k))){ set.add(s.charAt(k)); k++; } max = Math.max(max,set.size()); } return max; }}Copy the code

In the for loop above, I corresponds to left, k corresponds to right, and Max is the value that stores the longest string. The characters in the window are stored by Set, redetermination is performed by the contains method of Set, and obtaining the maximum value is performed by the Math Max method.

Finally, the time complexity of this algorithm is O(n), where n is the length of the string. Left and right Pointers traverse the entire string once each.

summary

In this article, we should focus on learning the principle and steps of sliding Windows. After mastering the knowledge of sliding Windows, LeetCode is just an example of sliding Windows. For algorithm problems, never memorize the solution code.

Three things to watch ❤️

If you find this article helpful, I’d like to invite you to do three small favors for me:

  1. Like, forward, have your “like and comment”, is the motivation of my creation.

  2. Follow the public account “Java rotten pigskin” and share original knowledge from time to time.

  3. Also look forward to the follow-up article ing🚀

  4. [666] Scan the code to obtain the learning materials package