003._longest_substring_without_repeating_characters.md

###3. Longest Substring Without Repeating Characters

题目: https://leetcode.com/problems/longest-substring-without-repeating-characters/

难度:

Medium

思路

粗一看是dp，细一看是greedy

idx	0	1	2	3	4	5	6	7
	a	b	c	a	b	c	b	b
rnd	↑        stop↑
		↑       stop↑
		    ↑           stop↑

因为其实只要每次记录下重复开始的位置，就可以解决问题。

注意最后还有一个 n - start 和 l 来比较，这相当于是最后一个round

如果当前重复的这个s[i]取值是限定大于start，就是在start之后再出现重复

class Solution(object):
	def lengthOfLongestSubstring(self, s):
		"""
		:type s: str
		:rtype: int
		"""
		n = len(s)
		l = 0
		maps = {}
		start = 0

		for i in range(n):
			if maps.get(s[i],-1) >= start:
				l = max(i - start, l)
				start = maps.get(s[i]) + 1
				print start
			maps[s[i]] = i
		return max(n - start, l)