Intermediate Level
Implement the longestSubstringWithoutRepeat method that returns the length of the longest substring that has no repeated characters.
The input contains a string text. Your task is to return the length of the longest contiguous substring that does not contain repeated characters.
A substring must use consecutive characters from the original string. 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 where the current window always contains unique characters.
Move the right pointer through the string. If the current character was already seen inside the current window, move the left pointer after its previous position. Update the best length after each step.
Pseudocode:
function longestSubstringWithoutRepeat(text):
left = 0
best = 0
lastSeen = empty map
for right from 0 to length(text) - 1:
current = text[right]
if current exists in lastSeen and lastSeen[current] >= left:
left = lastSeen[current] + 1
lastSeen[current] = 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