Shulou(Shulou.com)06/02 Report--

How to find the longest substring without repetition in LeetCode? I believe many inexperienced people don't know what to do about it. Therefore, this paper summarizes the causes and solutions of the problem. Through this article, I hope you can solve this problem.

Topic description:

Given a string, please find out the length of the longest substring that does not contain repeating characters.

Example:

Input: s = "abcabcbb" output: 3 explanation: because the longest substring without repeating characters is "abc", its length is 3. Title description

The problem is simply to find the length of the longest substring that does not contain repeating characters from a string.

If the problem is judged by the method of exorbitant profits, the time complexity will directly become O (n ^ 2), which is more frightening. Therefore, the method of sliding window can be adopted to reduce the time complexity.

What is a sliding window?

The sliding window algorithm operates on a specific size string or array instead of the entire string and array, which reduces the complexity of the problem and thus the nesting depth of the loop. Sliding windows are mainly used in arrays and string scenarios.

Simple exampl

First, let's take a look at the operation of the sliding window through a simple example. For example, there is an array [1-window 3-5-Magne2] that sets the size of the sliding window to 3. When the window slides from the starting position of the array to the final position, the sum of 3 elements in each window is calculated in turn, which is represented as sum.

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

The above figure is an example, when the window is located in [1Power3], after processing the data of the window, move the window one grid to the right, which is equivalent to cutting off the 1 on the left side of the original window, and then adding the 6 on the right side 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 the xx that satisfies the x-most interval of xx (substring, subarray)."

The basic steps of sliding a window

It should be noted that the movement of the window is carried out in the order in which it moves; the size of the window is not necessarily fixed and can be continuously shrunk or enlarged.

For the basic problem-solving idea of the sliding window algorithm, the string S example is as follows:

(1) use double pointers to specify the range of the window, initialize the left=right=0, and the indexed interval [left,right] is a window.

(2) increase the right pointer of the window until the string in the window meets the condition.

(3) at this point, stop the increase of right and increase the left pointer to shrink the window [left,right] until the string in the window no longer meets the requirements. Each time you add left, you need to update the results of the round.

Repeat steps 2 and 3 until right reaches the end of the string.

Among them, the second step is equivalent to finding a "feasible solution", and then the third step is to optimize the "feasible solution" and finally find the optimal solution. The left and right pointers move forward in turn, the window size increases or decreases, and the window continues to slide to the right.

Solve a problem

After learning about window sliding, we go back to the topic of LeetCode, changing the fixed window of the above example into a variable size window, and replacing the sum with determining whether it contains a specified character.

Therefore, apply the above ideas to carry on the analysis. Take the string "dvdf" as an example, use the following figure to demonstrate the process of sliding.

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

(1) Select the initial value left=right=0, that is, the window [0J0].

(2) determine whether the character on the right of right already exists in the window.

(3) if you find that the character v is not in the window, you can move right one bit to the right, and the window becomes [0pc1]

(4) continue to expand the right boundary, right=2, and stop moving to the right if you find that d already exists in the window.

(5) at this time, the length of the window is the length of the substring enabled by d. Compare the current window length with the historical max (default value 0), and find that 2 > 0, so update max to 2.

(6) start to move the left, and the window changes to [1]

(7) continue to expand the right boundary and find that d does not exist in the window, and the window becomes [1pc2]

(8) continue to expand the right boundary and find that f does not exist in the window, and the window becomes [1p3]

(9) reach the maximum length of the string, stop moving to the right, compare the current window length with the historical max size, and find that 3 > 2, so update max to 3.

(10) the length of the longest substring without repeating characters is obtained.

After understanding the above steps, let's take a look at the Java code implementation of the original topic:

Class Solution {public int lengthOfLongestSubstring (String s) {int n = s.length (); int k = 0, max = 0; Set set = new HashSet (); for (int iTuno; I < n; iLiv +) {if (I! = 0) {set.remove (s.charAt (iMul 1)) } while (k < n & &! set.contains (s.charAt (k) {set.add (s.charAt (k)); max = Math.max (max,set.size ());} return max }} after reading the above, do you know how to find the longest substring in a string without repetition in LeetCode? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.