Prompt:
"Given a string s, find the length of the longest substring without repeating characters."
This problem gave me a few issues that made me realize the importance of solving a problem in comparison to solving it well. While the final submission ended up being incredibly inefficient (especially compared to the rest of the LeetCode community's runtimes for this problem), the problem was indeed solved and all test cases were passing. This isn't to say that the solution shouldn't be improved upon now that it "works", but rather that limiting your choices based on self-imposed requirements (in this case, not using nested for loops). But that's another matter entirely. On to the problem!
I initially tried to write a method that would use counters to iterate through the list, adding characters to a "used" list and cashing out on that list's length when a duplicate character was found. This method eventually became capable enough to pass around 40% of test cases (which, at the time, was the highest I'd gotten for the problem). Eventually it became clear that this method couldn't possibly work because it didn't check possible substrings, but rather checked based entirely upon position (thus ignoring substrings where the duplicated character isn't necessarily the next character in the string; e.g. "abac" would return 2 because it wouldn't consider "bac" after reaching the second "a").
One of my better attempts:
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
longest = 0
counter = 0
used = []
if len(s) == 0:
return 0
if s == " " or len(s) == 1:
return 1
for i in range(0, len(s)):
if s[i] in used:
print(used)
if counter > longest:
longest = counter
counter = 1
used = []
used.append(s[i])
else:
used.append(s[i])
counter += 1
if counter > longest:
longest = counter
return longest
The solution that ended up working started with a more math-oriented approach. The longest possible substring in a string is the length of the string, and it follows that the longest non-character-repeating substring possible is limited by the number of characters in the string. As such, this solution takes the string and, after determining the longest possible substring available, checks substrings of the string iteratively until a match is found. While this isn't the prettiest solution, I'm happy that I both finally managed to finish this problem and made the "chunk-checking" loops scalable, something I hadn't considered doing for these exercises in the past. Maybe in the future I'll come back and solve this problem more efficiently, but for now, it's probably best to move on.
As always, the solution code:
class Solution:
def unique(s):
chars = []
for i in range(0,len(s)):
if s[i] not in chars:
chars.append(s[i])
return len(chars)
def lengthOfLongestSubstring(self, s: str) -> int:
maxstr = Solution.unique(s)
if len(s) == 0:
return 0
if s == " " or len(s) == 1:
return 1
for i in range(maxstr, 0, -1): #outer control loop for chunking
for j in range(0, (len(s)-i+1)):
test = s[j:(j+i)]
temp = Solution.unique(test)
if temp == i:
return i