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.
解1（暴力解）：
遍历字符串，列出所有的子字符串的集合，然后判断子字符串是否有重复的元素。boolean allUnique(String s, int start, int end)来判断start和end之间是否有重复的字符串。
代码如下(java)：
public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); int ans = 0; for (int i = 0; i < n; i++) for (int j = i + 1; j <= n; j++) if (allUnique(s, i, j)) ans = Math.max(ans, j - i); return ans; } public boolean allUnique(String s, int start, int end) { Set<Character> set = new HashSet<>(); for (int i = start; i < end; i++) { Character ch = s.charAt(i); if (set.contains(ch)) return false; set.add(ch); } return true; } }
这种方式的时间复杂度为O(n^3),
空间复杂度为O(k),k最大为不重复的子字符串的长度。。这种方法显然不是最优解，提交时会显示时间超时。
解2(推拉窗)：
创建一个hashset，用两个变量i，j分别表示子字符串的首尾位置。从字符串的首字符添加字符，如果在添加一个字符的时候，判断hashset中是否已经存在，如果不存在，添加该字符到set，进行下一个字符的判断，更新返回的长度值；否则，删除i位置的字符，子字符串的首位置向后移一位，如此循环先去。
代码(java)：
public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(); Set<Character> set = new HashSet<>(); int ans = 0, i = 0, j = 0; while (i < n && j < n) { // try to extend the range [i, j] if (!set.contains(s.charAt(j))){ set.add(s.charAt(j++)); ans = Math.max(ans, j - i); } else { set.remove(s.charAt(i++)); } } return ans; } }
该算法的时间复杂度为O(2n)=O(n).
空间复杂度为O(k),k最大为不重复的子字符串的长度。
解3(推拉窗改进)：
上面遍历的两次字符串，我们可以将下标和字符存成字符串，那么我们就不必一步一步的递增i了。代码如下(java)。
public class Solution { public int lengthOfLongestSubstring(String s) { int n = s.length(), ans = 0; Map<Character, Integer> map = new HashMap<>(); // current index of character // try to extend the range [i, j] for (int j = 0, i = 0; j < n; j++) { if (map.containsKey(s.charAt(j))) { i = Math.max(map.get(s.charAt(j)), i); } ans = Math.max(ans, j - i + 1); map.put(s.charAt(j), j + 1); } return ans; } }
空间复杂度不变，时间复杂度为O(n),只遍历字符串一次。
