Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

思路一：
使用hash表

  1. 变量start记录了子串的起点。
  2. used用来记录字符串的字符，key是字符c，value是索引i。
  3. 如果字符之前出现过，start右移，否则，更新最大长度。

实现：

1
2
3
4
5
6
7
8
9
10
def lengthOfLongestSubstring(self, s):
        used = {}
        max_len = start = 0
        for i, c in enumerate(s):
            if c in used and start <= used[c]:
                start = used[c] + 1
            else:
                max_len = max(max_len, i-start+1)
            used[c] = i
        return max_len

备注：注意当前子串的长度为i-start+1。