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.
提示：提交代码后，需要用简洁的语言解释一下代码思路~ 谢谢
历史题目和总结见公众号「每日一道算法题」
https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
难度:
Medium
粗一看是dp，细一看是greedy
我们先从第一个字符开始，只要碰到已经出现过的字符我们就必须从之前出现该字符的index开始重新往后看。
例如‘xyzxlkjh’，当看到第二个‘x’时我们就应该从y开始重新往后看了。
那么怎么判断字符已经出现过了呢？我们使用一个hashmap，将每一个已经阅读过的字符作为键，而它的值就是它在原字符串中的index，如果我们现在的字符不在hashmap里面我们就把它加进hashmap中去，因此，只要目前的这个字符在该hashmap中的值大于等于了这一轮字符串的首字符，就说明它已经出现过了，我们就将首字符的index加1，即从后一位又重新开始读，然后比较目前的子串长度与之前的最大长度，取大者。
最后还要进行一次比较，因为最后一次没有比较，即 n - start 和 l (字母L) 的比较，这是最后一个round
python
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
l, start, n = 0, 0, len(s)
maps = {}
for i in range(n):
if maps.get(s[i], -1) >= start:
l = max(l, i - start)
start = maps.get(s[i]) + 1
maps[s[i]] = i
return max(l, n - start)
class Solution {
public int lengthOfLongestSubstring(String s) {
HashMap
map = new HashMap
();
int l= 0;
int start = 0;
int n = s.length();
for (int i = 0; i < n; i++){
if(returnDef(map, s.charAt(i)) >= start){
l = Math.max(l, i-start);
start = map.get(s.charAt(i)) + 1;
}
map.put(s.charAt(i), i);
}
return Math.max(n-start,l);
}
public int returnDef(HashMap
map, Character c){
if (map.get(c) == null){
return -1;
}
return map.get(c);
}
}
谢谢Keqi Huang的无私的总结，欢迎大家打赏。
