Given a string S, find the largest substring with no repetition i.e. largest substring which contain all unique characters.
def lengthOfSubstring(s):
dic = {}
left = -1
res = 0
for i in range(len(s)):
if s[i] in dic and dic[s[i]] > left:
left = dic[s[i]]
dic[s[i]] = i
res = max(res, i-left)
return res
s = input()
print(lengthOfSubstring(s))
For the above problem to solve , what changes will make the above code work fine.
let me share my approach :-
Approach: The idea is to traverse the string and for each already visited character store its last occurrence in a hash table(Here unordered_map is used as hash with key as character and value as its last position). The variable st stores starting point of current substring, maxlen stores length of maximum length substring and start stores starting index of maximum length substring. While traversing the string, check whether current character is present in hash table or not. If it is not present, then store current character in hash table with value as current index. If it is already present in hash table, this means the current character could repeat in current substring. For this check if the previous occurrence of character is before or after the starting point st of current substring. If it is before st, then only update the value in hash table. If it is after st, then find length of current substring currlen as i-st, where i is current index. Compare currlen with maxlen. If maxlen is less than currlen, then update maxlen as currlen and start as st. After complete traversal of string, the required longest substring without repeating characters is from s[start] to s[start+maxlen-1].
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.