给定string S的length N发现最长的串不重复的字符。
string S
length N
例:
输入: “ stackoverflow”
输出: “ stackoverfl”
如果有两个这样的候选者,则从左开始返回。我需要线性时间和恒定空间算法。
您将需要一个字符串的开始和结束定位符(/ pointer),以及一个用于存储每个字符信息的数组:它是否至少发生了一次?
从字符串的开头开始,两个定位符都指向字符串的开头。
将结束定位符向右移动,直到找到重复(或到达字符串的末尾)为止。对于每个处理的字符,将其存储在数组中。停止后,存储位置(如果这是最大的子字符串)。还请记住重复的字符。
现在,使用开始定位器执行相同的操作,在处理每个字符时,从数组中删除其标志。移动定位器,直到找到较早出现的重复字符。
如果尚未到达字符串末尾,请返回步骤3。
总体:O(N)