pythonalgorithmsubstringlongest-substring

Find longest substring without repeating characters (LeetCode)


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!


Solution

  • 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)