(Medium #3) 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 

My solution (develop)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        chrlist = []

        # start point
        for i in range(len(s)):
            if s[i] not in chrlist:
                chrlist.append(s[i])
            else:
                if len(chrlist) > max_len:
                    max_len = len(chrlist)
                    result = chrlist

                pos = chrlist.index(s[i])
                chrlist = chrlist[pos+1:]
                chrlist.append(s[i])
        if len(chrlist) > max_len:
            max_len = len(chrlist)
        # print(result)

        return max_len
Runtime100 ms / Memory: 14.1MB

My solution (original)

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        max_len = 0
        # start point
        for i in range(len(s)):
            chrlist = [s[i]]
            
            # add next character
            for k in range(i+1, len(s)):
                if s[k] in chrlist:
                    break
                chrlist.append(s[k])
            
            if len(chrlist) > max_len:
                max_len = len(chrlist)
                # result = chrlist
        
        # print(result)
        return max_len
Runtime: 1700ms / Memory: 13.9MB

댓글