通过滑动窗口确定无重复字符的最长子串

Question

给定一个字符串s，编写算法找出其中不含有重复字符的最长子串的长度。

题设要求子串中不出现重复字符，因此可以在遍历过程中将出现过的字符的位置记录在数组中。在出现过的字符再次出现后，当前子串便不再满足条件，因此需要更新子串的起始位置从而重建新子串。

同时，在遍历过程中还需记录每一步的子串长度，并将其与最长子串长度相比较，若大于最长子串长度则对其进行更新。

以字符串“abcabc”为例，首先定义用于遍历数组与充当子串尾指针的变量end，以及子串起始指针start。为了避免子串中出现重复字符，定义一个数组index，其具有两个功能

• 用于记录字符串中每个字符在之前是否出现过
• 用于存储出现重复字符时start应移动到的位置

其中的127位分别对应ASCII码中的前127位。最后定义用于记录子串当前长度的变量length与子串最大长度max_length。

int start = 0;
int end;
int index[128] = {0};
int length = 0;
int max_length = 0;

对于遍历过程中遍历到的每个字符，定义其index值为end + 1。若某个字符的index值大于start，则说明start值需要更新，即子串中出现了重复字符。此时，在更新子串前，记录当前子串的长度，将其与最大长度比较，并根据比较结果对其进行更新。具体代码如下：

for(end = 0;s[end]!='\0';end++){
  if(index[s[end]] > start){
    length = end - start;
    if(length > max_length){
      max_length = length;
    }
    start = index[s[end]];  //更新start
  }
  index[s[end]] = end + 1;  //记录字符串中每个字符的index值
}
length = end - start;
return length>max_length?length:max_length;

依照此逻辑执行操作直至遍历至字符串结尾，其完整代码如下：

int lengthOfLongestSubstring(char* s){
  int start = 0, end, index[128] = {0}, length = 0, max_length = 0;
  for(end = 0;s[end]!='\0';end++){
    if(index[s[end]] > start){
      length = end - start;
      if(length > max_length){
        max_length = length;
      }
      start = index[s[end]];  //更新start
    }
    index[s[end]] = end + 1;  //记录字符串中每个字符的index值
  }
  length = end - start;
  return length>max_length?length:max_length;
}

Python下代码如下

class Solution(object):
  def lengthOfLongestSubstring(self, s):
    if not s:
      return 0
    max_length = 0
    start, end = 0, 0 
    for i, c in enumerate(s):
      if c not in s[start:end]:
        end += 1
      else:
        start += s[start:end].index(c) + 1
        end += 1
      max_length = max(end - start, max_length)
    return max_length if max_length != 0 else len(s)

​