Very easy Python Solution in O(n)-time.


  • 6

    Main idea:

    1. Loop for the string s, and use a list called temp to save the characters that are in a continuous non-repeated sub-string.
    2. If character s[i] not in temp, then add it to temp.
    3. If character s[i] in temp, update result if the length of temp is greater than result(who records the longest sub-string length). Then delete from temp the characters that are in front of s[i], and add s[i] to tail of temp.
    4. Loop to end of s, return result.

    Code:

    class Solution(object):
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            result=0
            temp=[]
            for item in s:
                if item in temp:
                    if len(temp)>result:
                        result=len(temp)
                    temp=temp[temp.index(item)+1:]
                    temp.append(item)
                else:
                    temp.append(item)
            return max(len(temp),result)
    

    Hint:

    DP could be better leveraged to complicated problems. Try to design simple logic for easy problems.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.