start

import time

def (fn):
    def wrapper(*args):
        s = time.time()
        ret = fn(*args)
        print ret, "use: %s" % round(time.time() - s, 4)
        return ret
    return wrapper


class Solution(object):

    # 3. Longest Substring Without Repeating Characters


    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        i = 0
        cache = {}
        ret = 0

        for i in range(len(s)):
            ch = s[i]
            if ch in cache:
                j = cache[ch]
                # 因为是map，j不一定是最小的index，需要min(cache.itervalues())
                ret = max(ret, i - min(cache.itervalues()))
                # 每次重新搞一个新的map来记录新的没有重复的字符串
                cache = dict(filter(lambda x: x[1] > j, cache.iteritems()))
            else:
                if cache:
                    ret = max(ret, i - min(cache.itervalues()) + 1)
                if i == 0:
                    ret = 1

            cache[ch] = i

        return ret


    def recommend_longest_substring_without_repeat(self, s):
        used_chars = {}
        start = max_length = 0
        for i in range(len(s)):
            if s[i] in used_chars and start <= used_chars[s[i]]:
                start = used_chars[s[i]] + 1
            else:
                max_length = max(max_length, i - start + 1)
                used_chars[s[i]] = i
        return max_length