leetcode-3 求一串字符串中不重复的最长子字符串

题目

'''
Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
'''

给定一个字符串，求其不重复的最长子字符串的长度。

分析

设置一个头指针和尾指针，用一数组存储已经出现的字符，每次循环尾指针向后移动一位，将新出现的元素加入到数组中，如果新进元素在书中出现，定位到上次出现的位置，将数组切片后，组成新的数组。头指针设置为上一次元素出现的位置的后一位，循环这个过程。如果不存在，判断当前数组的长度是否大于当前最大长度，大的话新的数组长度为最大长度， 否则最大长度不变。

代码

if len(s) <= 1:
      return len(s)

  substr = ''
  start = end = max_length = 0

  while end < len(s):
      if s[end] not in substr:
          substr += s[end]
          if len(substr) > max_length:
              max_length = len(substr)
          end += 1
      else:
          position = substr.index(s[end])
          substr += s[end]
          start = position + 1
          substr = substr[start:]
          end += 1

  return max_length

更进一步

O(n)算法的本质是 查找新出现的元素是否在以前出现过，如果出现过，则判断尾指针和头指针的距离是否大于当前保存的最大长度，是则更新最大长度，否则，将头指针移到上次出现的位置的下一个位置。

新代码

start = maxl = 0

used = {}

for i in range(len(s)):
    if s[i] in used and start <= used[s[i]]:
        start = used[s[i]] + 1
    else:
        maxl = max(maxl, i - start + 1)
    
    used[s[i]] = i            

return maxl

代码简洁度是不是提升了一个层次呢？