python-3.x - 最长子字符串及其长度，不包含重复字符

Question

def findLongestSubstring(string):
  st = 0  # starting point of current substring.
  maxlen = 0 # maximum length substring without repeating characters.
  start = 0 # starting index of maximum length substring.
  pos = {} # Hash Map to store last occurrence of each already visited character
  pos[string[0]] = 0 #Last occurrence of first character is index 0

  for i in range(1, len(string)):
    # If this character is not present in hash, character, store this in hash.
    if string[i] not in pos:
      pos[string[i]] = i
    else:
      # If this character is present in hash then check if that occurrence
      # is before or after starting point of current substring.
      if pos[string[i]] >= st: 
                # find length of current substring and update maxlen and start accordingly.
        currlen = i - st
        if maxlen < currlen:
          maxlen = currlen
          start = st

        # Next substring will start after the last occurrence of current
        # character to avoid its repetition.
        st = pos[string[i]] + 1

      pos[string[i]] = i # Update last occurrence of current character.

  # Compare length of last substring with maxlen & update maxlen and start accordingly.
  if maxlen < i - st:
    maxlen = i - st
    start = st

  # The required longest substring without repeating characters is from string[start]
  #to string[start+maxlen-1].
  print("Lenth is:", len(string[start : start + maxlen]) )
  print( string[start : start + maxlen] )
  return string[start : start + maxlen]

上面的代码大部分都有效。但是对于下面的测试用例，它失败了。我究竟做错了什么？代码是从 GeeksforGeeks 复制的。代码返回“ba”，而不是“bad”。

assert(findLongestSubstring("babad") == "bad" )

标签： python-3.x

Answer 1

Your last length check should work if you increment i by 1.

  # Compare length of last substring with maxlen & update maxlen and start accordingly.
  if maxlen < (i + 1) - st:
    maxlen = (i + 1) - st
    start = st