[Python] Optimizing brute force approach to Longest Substring Without Repeating Characters

I'm trying to improve my Python by solving some problems on LeetCode.

I'm currently working on the Longest Substring Without Repeating Characters 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.​

I am trying to do brute forcing, by finding all substrings and then finding the longest one:

def lengthOfLongestSubstring(self, s: str) -> int:
list_of_values = [0]
if (not s):
return 0

new_list = list(s[0])
i = 1
size_s = len(s)
while i < size_s:
if s not in new_list:
new_list.append(s)
i += 1
else:
list_of_values.append(len(new_list))
new_list = []
s = s[1:]
i = 0
size_s = len(s)
if size_s < max(list_of_values):
break
return max(max(list_of_values), len(new_list))


The solution works, but it times out for the last test case on LeetCode (a very long string). Does anyone have suggestions on how to make this faster?

Continue reading...