一尘不染

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

algorithm

给定string Slength N发现最长的串不重复的字符。

例:

输入: “ stackoverflow”

输出: “ stackoverfl”

如果有两个这样的候选者,则从左开始返回。我需要线性时间和恒定空间算法。


阅读 170

收藏
2020-07-28

共1个答案

一尘不染

  1. 您将需要一个字符串的开始和结束定位符(/ pointer),以及一个用于存储每个字符信息的数组:它是否至少发生了一次?

  2. 从字符串的开头开始,两个定位符都指向字符串的开头。

  3. 将结束定位符向右移动,直到找到重复(或到达字符串的末尾)为止。对于每个处理的字符,将其存储在数组中。停止后,存储位置(如果这是最大的子字符串)。还请记住重复的字符。

  4. 现在,使用开始定位器执行相同的操作,在处理每个字符时,从数组中删除其标志。移动定位器,直到找到较早出现的重复字符。

  5. 如果尚未到达字符串末尾,请返回步骤3。

总体:O(N)

2020-07-28