Intermediate Level
Implement the longestSubstringNoRepeat method that returns the length of the longest substring without repeated characters.
The input contains a string text. Your task is to return the length of the longest substring that does not contain any repeated character.
A substring must be continuous. For example, in abcabcbb, the longest substring without repeating characters is abc, so the answer is 3.
Example 1
Input
text (string) =
abcabcbbReturns (int)
3Example 2
Input
text (string) =
bbbbbReturns (int)
1Example 3
Input
text (string) =
pwwkewReturns (int)
3Use a sliding window to keep a substring with unique characters.
Move the right side of the window one character at a time. If the current character was already seen inside the current window, move the left side just after the previous occurrence of that character.
After each step, update the maximum window length.
Pseudocode:
function longestSubstringNoRepeat(text):
lastSeen = empty map
left = 0
best = 0
for right from 0 to length(text) - 1:
ch = text[right]
if ch exists in lastSeen and lastSeen[ch] >= left:
left = lastSeen[ch] + 1
lastSeen[ch] = right
best = max(best, right - left + 1)
return bestReady to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run