# Longest Substring Without Repeating Characters

## # Solution

Let $n$ be size of the string, $m$ the size of the charset/alphabet.

### # Brute Force

The brute force solution is not shown.

Complexity:

• time: $O(n^3)$
• a nested for loop for the sliding window and to check if unique takes $O(n)$ time
• space: $O(\min(m,n))$
• $O(k)$ space for the sliding window, where $k$ is the size of the Set, which is upper bounded by $n$ and $m$

### # Sliding Window Using HashSet

The idea is to use a sliding window to locate a substring, and a HashSet st to see if the new char is already seen previously.

Sliding window logic: i is the left boundary and j the right boundary. Increase j by 1 if s[j] has not occurred in the current subarray. Increase i if s[j] has occurred.

Invariant: i<=j

Complexity:

• time: $O(n)$
• worst case $O(2n)$: all characters are the same and each will be visited by both $i$ and $j$
• space: $O(\min(m,n))$
def lengthOfLongestSubstring(self, s: str) -> int:
if not s: return 0
n = len(s)
st = set()
i = j = 0
res = 1
while i<n and j<n:
if s[j] not in st:
j += 1
res = max(res, j-i)
else:
st.remove(s[i])
i += 1
return res


### # Sliding Window Using HashMap

If having seen the new char in existing window, could update the left boundary to d[val]+1 ($1$ + index of last duplicate in the window).

Several optimizations:

1. start and idx rather than i and j to refer to left and right boundaries of window
2. enumerate idx and val
3. dct to store the mapping from val to idx

Complexity:

• time: $O(n)$
• space: $O(\min(m,n))$
def lengthOfLongestSubstring(self, s: str) -> int:
res = 0
start = 0
dct = {}
for idx, val in enumerate(s):
if s[idx] in dct:
start = max(start, dct[val]+1)
res = max(res, idx-start+1)
dct[val] = idx
return res

Last Updated: 7/19/2020, 3:45:14 PM