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

Python how to achieve the longest string of leetcode non-repetitive characters, many novices are not very clear about this, in order to help you solve this problem, the following editor will explain in detail, people with this need can come to learn, I hope you can get something.

The longest string without repeating characters is the subject of a string processing algorithm, which is a common task in daily programming. Use Python to realize the algorithm problem of leetcode, which will involve a concept "sliding window".

Description of the topic

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

Example 1: input: "abcabcbb" output: 3 explanation: because the longest substring without repeating characters is "abc", its length is 3.

Example 2:

Input: "bbbbb" output: 1 explanation: because the longest substring without repeating characters is "b", its length is 1.

Example 3:

Input: "pwwkew" output: 3 explanation: because the longest substring without repeating characters is "wke", its length is 3. Please note that your answer must be the length of the substring. "pwke" is a subsequence, not a substring. Second, the way to solve the problem

Let's first define a "substring". According to the title description, "substring" is the truncation of a part of a string with a length from 1 to the length of the string. For example, the substring set of "abc" is:

['ab',' baked, 'crested,' ab', 'bc',' abc']

It's easy to generate this collection with Python. Did you think of that?

Def subs (s: str): results = [] for begin in range (len (s)): for length in range (len (s)-begin): results.append (s [begin: begin + length + 1]) return resultsz = subs ('abcde') print (z)

So the question is, how many such "substrings" are there in any string of length n? The answer is: (nasty 1) * n / 2. It is easy to get this answer from the above example: when begin is equal to 0, the length can be n-0, begin is equal to 1, the length can be n-1, and so on, the total is:

N + (nMel 1) + … + 1 = > (nasty 1) * n / 2

(1) violent solution

After understanding the concept and acquisition method of "substring", we naturally get the simplest and most "violent" solution: traversing the string to get all the "substrings", and then judging whether each "substring" has repeated characters or not. you'll end up with the longest substring without repetition.

In this "violent" algorithm, the time complexity of calculating all substrings is O (N2), while judging whether a substring has duplicate characters, and traversing the string from beginning to end, all the final time complexity can reach O (N2).

This solution is not acceptable, it is all mentioned because of the previous explanation of "substring" and its quantity calculation, to practice the operation of Python on strings.

(2) sliding window

The concept of "sliding window" is very common in computer algorithms. This algorithm can transform a nested loop into a single loop and reduce the time complexity. It is used in many different fields:

The sliding window of TCP protocol for flow control

N-gram in NLP (Natural language processing)

Object recognition in Image processing

Interested students can have an in-depth understanding of the application areas mentioned above.

Let's take a look at how the "sliding window" handles strings. Combined with the example "abcabcbb" in the title, let's take a look at how to find its longest unrepeated substring.

First, we define both ends of the window: begin and end, which represent the beginning and end of the substring we are looking for, respectively.

In the beginning, both begin and end point to the position of 0, which is called'a', and then end moves backward (the window widens), and when it encounters the second'a'(when it encounters a repeated character), it gets a substring whose length is the difference between the position of end and begin.

Demonstration of non-repetitive longest string algorithm

How to tell if the duplicate character'a' has been encountered? You need a dictionary as an auxiliary data structure to put every character end encounters from scratch and its index position in the dictionary, and end can look it up every time he moves to a new character.

Through the dictionary, we can find the location of the first'a'in the dictionary when we encounter the second'a'. To continue the search for unrepeating substrings, begin points to the location of the first'a 'and the one after the' b'. Then end continues to move back to'b', and it is found that it repeats with the previous'b', calculating the substring length to be assigned to the maximum length (to be compared), and begin to move the position after the first'b', that is,'c'.

In this way, you can move the end to the end of the string in turn to find the longest substring, and the "substring window" is moved from beginning to end. All you need is a loop of end from beginning to end.

Implement this process in Python as follows:

Class Solution: def lengthofLongestSubstring (self, s: str)-> int: maxlen = 0 memo = dict () begin, end = 0,0 n = len (s) while end < n: last = memo.get (s [end]) memo [s]] = end if last is not None: maxlen = max (maxlen) End-begin) begin = max (begin, last + 1) end + = 1 maxlen = max (maxlen, end-begin) return maxlen

You can see the results after submission. "execution time" is just a reference. Once again, the result of submitting the same code is not to beat 91%, but to become more than 10%.

Is it helpful for you to read the above content? If you want to know more about the relevant knowledge or read more related articles, please follow the industry information channel, thank you for your support.

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.