Find longest substring without repeating characters (LeetCode)

Question

I am trying to solve this problem on LeetCode (https://leetcode.com/problems/longest-substring-without-repeating-characters/)

I got a code but i don't understand what's the problem with it.

def lengthOfLongestSubstring(s):
    letters = []
    counter = 0
    max_length = 0
    if s == '':
        return 0
    if len(set(s)) == 1:
        return 1
    for i in range(len(s)):
        print(s[i], max_length)
        if s[i] not in letters:
            letters.append(s[i])
            if i == 0:
                counter += 1
                continue
            elif s[i] != s[i - 1]:
                counter += 1
        else:
            if counter > max_length:
                max_length = counter
                letters = []
                letters.append(s[i - 1])
                letters.append(s[i])
                counter = 2
    return max(max_length, counter)


print(lengthOfLongestSubstring("pwwkew"))

I stuck on inputs "pwwkew" and "dvdf"... Program work different on these inputs. Probably i misunderstand the algorithm, so please correct me. Thanks!

Answer 1

Firstly you can create a function which checks if any character is repeated in a string. This can be done easily by converting the string into a set and checking if its length matches with the original string. if equal then the string had no repeated characters.

def repChars(s):
    if len(set(s))==len(s):return False
    else:return True

Secondly we define x and n to hold the position of the largest substring and its length.

n=0
x=''

third we 2D loop the string such that we sample a substring and check if has repeated characters. Accordingly if it was ok then we save it in our x and n if the previous value of n was smaller than the new one

for i in range(0,len(s1)):
    for j in range(i,len(s1)):
        if not repChars(s1[i:j+1]):
            if n<=len(s1[i:j+1]):
                n=len(s1[i:j+1])
                x=s1[i:j+1]
print(n,x)

the complete code below is

s='pwwkew'
s1=s
def repChars(s):
    if len(set(s))==len(s):return False
    else:return True
n=0
x=''
for i in range(0,len(s1)):
    for j in range(i,len(s1)):
        if not repChars(s1[i:j+1]):
            if n<=len(s1[i:j+1]):
                n=len(s1[i:j+1])
                x=s1[i:j+1]
print(n,x)

Answer 2

The main issue is your logic of discarding the whole substring whenever you see a repeated character and assigning i and i-1 characters as the new substring. In the case of "pwwkew", when you reach the second w, you assign "ww" as your new substring, which is not valid.

Additionally, your check in if s[i] not in letters is suboptimal, since checking for membership in a list is linear in the size of the input, and you can use more optimal data-structures, like a set/dictionary or keeping track of the index of the last time you saw the letter in a list, both of which would take constant time lookups.

Instead, you should remove letters from the start of the string until you have unique characters, then you can continue adding characters to your string. This is usually refered to as a two-pointer algorithm, as you keep track of potential pointers to the start and the end of the algorithm.

def lengthOfLongestSubstring(self, s: str) -> int:
    counter = [0]*256 #counter to keep track of number of occurances of characters
    ans = 0
    i, j = 0, 0
    while j < len(s):
        counter[ord(s[j])] += 1
        ans = max(ans, j-i+1)
        j += 1
        while j < len(s) and counter[ord(s[j])] != 0:
            counter[ord(s[i])] -= 1
            i += 1
    return ans

Alternatively, you can hash the last index you've seen the character in and obtain the solution as follows:

def lengthOfLongestSubstring(self, s: str) -> int:
    char_loc = {}
    ans, curr = 0,0
    for i,char in enumerate(s):
        if char in char_loc:
            curr = min(curr, i-char_loc[char]-1)
        char_loc[char] = i
        curr += 1
        ans = max(ans, curr)
    return ans