Leetcode Problem 3: Longest Substring Without Repeating Characters

(Attempted) solution Link to heading

The description of this problem seemed straightforward and as such I figured the implementation would also be the same. Wrong!

The first cause of concern was this part from the description

Input: s = “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Notice that the answer must be a substring, “pwke” is a subsequence and not a substring.

Which implies that we not only need to keep track of occurrences of a certain character, but also its position, and its position from any of its identical neighbours, if any.

With that said, I tried a few approaches with similar implementations, but couldn’t solve this. I’ll probably look into it with a fresh mind at some point in the future, but I’ve attached my current Python attempt below.

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n == 0:
            return 0
        elif n == 1:
            return 1
        elif n == 2:
            if s[0] != s[1]:
                return 2
            else:
                return 1

        chains = []
        chain = []

        for i in range(n):
            if s[i] not in chain:
                chain.append(s[i])
            else:
                # find first occurrence of elem and start counting substring that index + 1
                index = s.index(s[i])
                chain = list({char for char in s[index + 1:i + 1]})

            chains.append(len(chain))

        return max(chains)