题目描述
Given a string, find the length of the longest substring without repeating characters.
Solution:
思路
从左往右loop一遍，通过update开始与结尾的index，找出最长且符合要求的区间。
Detail
- 用set S记录current区间中已有元素，用int count记录目前为止最长的长度，开头i，结尾j
- i 和 j都从0开始，对于s中的每个新的char (即 j 所指元素):
a. 若不在S中，说明 current区间 可以扩展，j往后移动并且把该char加入S，同时看是否需要更新count，此时 i 不变
b. 若在S中, 说明已经达到 从 i 算起 符合要求的最长区间， 此时将s[i] 从S中移除，并将 i 往后移动一位，此时 j 不变，且count无需更新 - 当 j 到达s尾时结束
- 返回count
Complexity
- Time: O(n)
- Space: O(n)
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
n = len(s)
count = 0;
S = set()
i = 0
j = 0
while (j < n):
if (s[j] not in S):
S.add(s[j])
j += 1
count = max(count, j-i)
else:
S.remove(s[i])
i += 1
return count
后续
Solve it without using "set S"
