Longest Substring Without Repeating Character

Jack-Cherish · Jack-Cherish · commit 2fc9fde84a84 · 2017-10-10T09:54:59.000+08:00
diff --git a/String/Medium/3.Longest Substring Without Repeating Characters.md b/String/Medium/3.Longest Substring Without Repeating Characters.md
@@ -0,0 +1,35 @@
+# 题目
+
+给定一个字符串，找到最长无重复子字符串。
+
+**举例：**
+
+ - 给定的“abcabcbb”，答案是“abc”，长度为3。
+ - 给定的“bbbbb”，答案是"b"，长度为1。
+ - 给定的“pwwkew”，答案是"wke"，长度为3。注意是最长子字符串，不是最长子序列"pwke"。
+
+
+# 思路
+
+定义两个变量longest和left，longest用于存储最长子字符串的长度，left存储无重复子串左边的起始位置。
+
+然后创建一个哈希表，遍历整个字符串，如果字符串没有在哈希表中出现，说明没有遇到过该字符，则此时计算最长无重复子串，当哈希表中的值小于left，说明left位置更新了，需要重新计算最长无重复子串。每次在哈希表中将当前字符串对应的赋值加1。
+
+# 代码
+
+``` python
+class Solution(object):
+    def lengthOfLongestSubstring(self, s):
+        """
+        :type s: str
+        :rtype: int
+        """
+        longest = 0; left = 0; tmp = {}
+        for index, each in enumerate(s):
+            if each not in tmp or tmp[each] < left:
+                longest = max(longest, index - left + 1)
+            else:
+                left = tmp[each]
+            tmp[each] = index + 1
+        return longest
+```
