Is Python broken?

Question

I don't think it can get any faster than this:

class Solution:
    def lengthOfLongestSubstring(self, S):
        for i in xrange(len(S) - 1, 0, -1):
            for j in xrange(len(S) - i):
                s = S[j : j + i + 1]
                if len("".join(set(s))) == len(s):
                    return len(s)
        return 1

However, I am exceeding the time limit. What am I doing wrong?

Comments

maybe the time complexity of you algorithm is O(n^2)?

Answer 1

Here is an accepted python answer, just for your reference.

class Solution:
# @return an integer
def lengthOfLongestSubstring(self, s):
    if s is None:
        return None
    if len(s) == 0:
        return 0
    r_max = 0       # stores the length of the longest substring we currently see
    r_temp = ''     # a temporary string stores the current substring without repeating letters
    for i in xrange(len(s)):
        index = r_temp.find(s[i])
        if index == -1:     # s[i] not found in r_temp
            r_temp += s[i]  # so we add s[i] to r_temp
        else:               # s[i] is found in r_temp
            r_temp = r_temp[index+1:] + s[i]    # starts from found location + 1 with s[i]
        # update r_max if r_temp has a larger length
        if len(r_temp) > r_max:
            r_max = len(r_temp)
    return r_max