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.


  • 0
    R

    @J.R.Smith Thank you. This helped me a lot.


Log in to reply
 

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