一、题目描述
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：
s.length <= 40000
二、思路讲解
暴力方法，遍历字符串，以每一个字符作为开头，将它及后面的字符怼到HashSet中，如果怼不进去了，那就是重复了，此时集合的大小就是不重复的字串的大小。然后清空集合，再看下一个字符，直到遍历完整个字符串。效率较低。
三、Java代码实现
class Solution { public int lengthOfLongestSubstring(String s) { int len = s.length(); int index; HashSet<Character> set = new HashSet<>(); int big = 0; for(int i=0; i<len; i++){ index = i; set.clear(); //把字符后的每一个字符怼进集合中，直到怼不进（说明重复了）或者遍历完了字符串 while(index<len && set.add(s.charAt(index))){ index++; } big = Math.max(big, set.size()); } return big; } }
四、时空复杂度分析
时间复杂度： O(N^2)
空间复杂度： O(N)
五、代码优化
想想时间上的优化：能不能仅遍历一遍字符串呢？
我们可以使用滑动窗口的思想，或者是使用动态规划的思想。
再想想空间上的优化：能不能用常数级的空间呢？
可以用HashMap，在ASCII码內长度最多为128，占用空间为常数级。
1、滑动窗口
具体思路是：使用set存放滑动窗口内的所有字符。 set的大小即为滑动窗口的大小。
如果j指针处的字符能够插入set，证明不和滑动窗口内的字符重复，j指针后移，扩大窗口；
如果j指针处的字符不能插入set，说明字符出现重复，那就将i指针后移（同时从set中删掉i处字符），缩小窗口。
使用max始终保存set的长度的最大值。
class Solution { public int lengthOfLongestSubstring(String s) { Set<Character> set = new HashSet<>(); //滑动窗口内的所有字符 int max = 0; //最大无重复字串长度 int i=0; int j=0; while(j<s.length()){ if(set.add(s.charAt(j))){ //如果j处字符和窗口内字符不重复，j指针后移，扩大窗口 j++; } else { //如果j处字符和窗口内字符重复，i指针后移，缩小窗口（此时set内所有字符还是不重复的） set.remove(s.charAt(i)); i++; } max = Math.max(max, set.size()); } return max; } }
同样的道理，使用队列代替哈希集合来保存滑动窗口里的值，可以减少几次无用的判断，但是效率降低了。
class Solution { public int lengthOfLongestSubstring(String s) { Queue<Character> queue = new LinkedList<>(); //滑动窗口内的所有字符 int max = 0; //最大无重复字串长度 int i=0; int j=0; while(j<s.length()){ if(!queue.contains(s.charAt(j))){ //如果j处字符和窗口内字符不重复，j指针后移，扩大窗口 queue.add(s.charAt(j)); j++; } else { //如果j处字符和窗口内字符重复，i指针后移到重复字符之后 while(queue.poll() != s.charAt(j)){ i++; } } max = Math.max(max, queue.size()); } return max; } }
时间复杂度O（n）
空间复杂度O（n）
2、动态规划
遍历字符串，以每个字符作为结尾，curr表示以当前字符结尾的最大无重复长度，max保存最大的无重复长度。
在向后遍历的过程中，若第i个字符在前面出现过，假设出现在x位置，则curr为min{curr, i-x}，（大括号里的curr为前一个字符结尾的最大无重复长度）；若第i个字符在前面没出现过，则前一个长度直接+1即可：curr = curr+1。
class Solution { public int lengthOfLongestSubstring(String s) { Map<Character, Integer> map = new HashMap<>(); int max = 0; //最大无重复长度 int curr = 0; //当前无重复长度 for(int i=0; i<s.length(); i++){ Character c = s.charAt(i); curr = Math.min((curr+1), (i-map.getOrDefault(c, -1))); map.put(c, i); max = Math.max(max, curr); } return max; } }
时间复杂度： O(N)
空间复杂度： O(1)
