refer to: https://www.algoexpert.io/questions/Longest%20Substring%20Without%20Duplication
Problem Statement
Analysis
Code
def longestSubstringWithoutDuplication(string): # Write your code here. lastSeen = {}# hashmap to store the index of the lastSeen character(updated index of unique character) longest = [0,1] # initialize to itself (since in python the slice function will exclude the right range) startIdx = 0 # startIdx to traverse the whole string, update the start character in substring for i, char in enumerate(string): if char in lastSeen: # duplicate will occur if do nothing startIdx = max(startIdx, lastSeen[char] + 1) # update the startIdx, lastSeen character idx + 1 to exclude the lastSeen character if longest[1] - longest[0] < i + 1 - startIdx: #update the longest substring longest = [startIdx, i + 1] # the i+1 th character will be excluded lastSeen[char] = i # update the index of the lastSeen character return string[longest[0] : longest[1]]
Time and space complexity