Problem: Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1.

Solution: Longest Substring Without Repeating Characters, Python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# @Date : 2015-02-04 15:28:02
# @Author : NSSimacer
# @Version : 1.0
class Solution:
# @return an integer
def lengthOfLongestSubstring(self, s):
char_dict = dict()
start_index = 0
max_length = 0
for n, char in enumerate(s):
if char in char_dict:
start_index = max(start_index, dict[char] + 1)
char_dict[char] = n
max_length = max(max_length, n - start_index + 1)
return max_length

用一个字典 (dict) 存储字符串 s 中每个字符 (key) 和字符的索引 (value),如果有相同字符出现在 s 中,最长连续且不含重复字符的子串的初始位置置为重复字符索引加 1,同时子串最大长度也要相应发生变化。
时间复杂度 O(N),空间复杂度 O(1)。