LC003 - Longest Substring Without Repeating Characters

Problem

Given a string s, find the length of the longest substring without repeating characters.

Example

Input: s = "abcabcbb"

Output: 3

Explanation: The answer is "abc", with the length of 3.

Solution

Index array is 128 because there are only 128 ASCII characters. Time complexity is $O(n)$ with $O(1)$ space.

def lengthOfLongestSubstring(self, s: str) -> int:
	maxLen = 0
	asciiIndex = [-1] * 128
	left = 0
	
	for right in range(len(s)):
		if asciiIndex[ord(s[right])] >= left:
			left = asciiIndex[ord(s[right])] + 1
		asciiIndex[ord(s[right])] = right
		maxLen = max(maxLen, right - left + 1)
	
	return maxLen