CODEWITHSUNDEEP
python-3.x
usustarr
usustarr

Reputation: 418

Longest sub string and its length without repeated chars

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]

Above code works for the most part. But for below test case, it fail. What am I doing wrong? Code was copied from GeeksforGeeks. Code is returning "ba", instead of "bad". 

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

Upvotes: 0

Views: 31

Answers (1)

ItsPete
ItsPete

Reputation: 2368

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

Upvotes: 1

Related Questions