查找最长的子串不重复字符

问题描述

给定一个串S 的长度为N 找到最长子无重复字符。

示例：

输入：计算器

输出：stackoverfl

如果有两个这样的候选人，左起第一回。我需要线性时间和不断的空间算法。

解决方案

1. 您将需要在开始和结束定位器（/指针）字符串，您存储信息的每一个字符数组：做到了occour至少一次？

2. 开始在字符串的开头，这两个定位器指向开始的字符串。

3. 将最终定位到右侧，直到你找到重复（或达到串的结尾）。对于每个被处理的字符，将其存储到数组中。当停止存储位置，如果这是最大的子字符串。还记得重复字符。

4. 现在处理的时候做同样的事情与启动定位器，每一个字符，从数组中删除的标志。移动定位到找到重复的字符。

5. 回到步骤3，如果你还没有达到字符串的结尾。

总评：O（N）

Given a string S of length N find longest substring without repeating characters.

Example:

Input: "stackoverflow"

Output: "stackoverfl"

If there are two such candidates, return first from left. I need linear time and constant space algorithm.

解决方案

1. You are going to need a start and an end locator(/pointer) for thestring and an array where you store information for each character:did it occour at least once?

2. Start at the beginning of the string, both locators point to thestart of the string.

3. Move the end locator to the right till you finda repetition (or reach the end of the string). For each processed character, store it in the array.When stopped store the position if this is the largest substring. Also remember the repeated character.

4. Now do the same thing with the start locator, when processingeach character, remove its flags from the array. Move the locator tillyou find the repeated character.

5. Go back to step 3 if you haven't reached the end of string.

Overall: O(N)

这篇关于查找最长的子串不重复字符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！