# Problem

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

Example 1:

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

Example 2:

Input: "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

# Thought Process

• Brute force, nested loop to loop thru all the sub-strings
• use a list to store sub-string; and a dict whose key is the len of substring, and value is the substring
• return max len substring

# White Board

Below is the white board:

# Code

The brute force solution has some issues. But I thought about using shifting window to solve it

class Solution:
def lswp(self, my_str):
res = {}
for i in range(len(my_str)):
temp = []
temp.append(my_str[i])
for j in range(len(my_str)):
if my_str[j] not in temp:
temp.append(my_str[j])
else:
break
res[len(temp)] = "".join(temp)

return(max(res))

def test_lswp():
lswp = Solution().lswp("abcabcbb")
print(lswp)

test_lswp()


3

I think this brute force solution is not correct

# Complexity

• Time complexity is O(n**2), two nested loops
• Space complexity is O(n), as I did create additional dictionary and list to store the results

# Optimization

Use shifting-windows, and an ascii array to check if a char exists in the current sub-string

class Solution2:
def lswp2(self, s):
freq = [0] * 128
# use freq to store the freq of all the chars
l, r = 0, -1
# shifting window is s[l,r], with invalid init state
res = 0
# initially res is 0

while l < len(s):

# as long as l can still move to the right

if((r + 1 < len(s)) and (freq[ord(s[r+1])] == 0)):
# r can still move to the end
r += 1
freq[ord(s[r])] += 1

else:
# if s[r+1] already exists, a.k.k freq[ord(s[r+1])] = 1
# move l until s[r+1] doesn't exist in s[l, r]
# every l += 1, need to exclude s[l] first, so s[l] is not in s[l,r] no more
freq[ord(s[l])] -= 1
l += 1
res = max(res, r - l + 1)

if res == 0:
return 0

return res

def test_lswp2():
lswp2 = Solution2().lswp2("xxzqi")
print(lswp2)

test_lswp2()


4

Now the time complexity is O(n), space complexity is O(128) => O(1) since I use a space of 128 to store all ascii value