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

What this article shares to you is about the length of the longest non-repeating substring of a string. The editor thinks it is very practical, so I share it with you. I hope you can get something after reading this article. Let's take a look at it with the editor.

Topic description:

For a string, design an efficient algorithm to find the length of the longest non-repeating substring of the string.

Given a string An and its length n, return its longest unrepeated substring length. Ensure that the characters in An are all lowercase English characters and the length is less than or equal to 500.

Test sample:

"abcdbefgdchi", 12 returns: 8

I studied this question for a long time, but it was really hard to think about it. It took me a long time to write the code after reading other people's ideas.

Analysis:

First, define three helper variables:

Max_len: indicates the length of the longest non-repeating substring in a string, that is, the value returned by the function

Map: the most recent position of the character used to store the position before the string

Pre_len: the length of the substring used to store the longest non-repeating characters before the current position

Let's start with the main logic.

Traverse from the beginning of the string

If the character is not in map, the character and its subscript are inserted into the map, and the pre_len++

Compared with max_len, the larger one is assigned to max_len.

If the character already exists in map, the value corresponding to the character (that is, the most recent subscript of the character) is taken out and marked as pos_A

The current subscript minus pre_len is marked as pos_B, indicating the starting position of the longest non-repeating substring in front of it

At this point, there are three situations for pos_A and pos_B:

The first case: posA = = pos_B

The second case: pos_A > pos_B

The third case: pos_A

< pos_B 对于第一种情况来说，pre_len 大小不会改变。 对于第二种情况来说，pos_A 在 pos_B的右边，根据 pos_A 和 pos_B 所代表的含义可知道： 在距离当前很近的位置上，当前字符已经出现了重复，因此当前位置之前最长无重复字符子串的长度缩短了，如图所示： 因此，更新后的 pre_len 应该为 当前位置的下标减去 pos_A 对于第三种情况来说，pos_A 在 pos_B 的左边，根据 pos_A 和 pos_B 所代表的含义可知道： 在距离当前很远的位置上，当前字符出现了重复，这个位置比pos_B 还远，这么远的路径上，pos_B 处的字符早已出现了重复，因此当前位置之前最长无重复字符子串的长度应该为 当前位置到pos_A 的距离，如图所示 因此，更新后的 pre_len 应该为 当前位置的下标减去 pos_B + 1 更新后的pre_len 与max_len 进行比较，取其大者即可 注意，最后应该将map中当前位置字符的下标进行更新（千万不能漏掉） 于是乎一个完整的逻辑已经完成了，这样从头到尾遍历这个字符串，最终便可得到 字符串的最长无重复字符的子串长度 max_len 甚至还可以获得该字串，将其单独打印出来（这里留给读者自行实现，不难） 代码如下： int longestSubstring(string A, int n) { if (A.size() second; int pos_B = i - pre_len; if (pos_A >

Pos_B) {pre_len = I-pos_A;} else if (pos_B > pos_A) / / pos_A max_len) max_len = pre_len; m [A [I]] = I; / / Update map} return max_len } the above is the length of the longest non-repeating substring of a string. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

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.