Given a string, find the length of the longest substring without repeating characters.
Example:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Input: "pwwkew"
Output: 3
Explanation: 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.
难度：Medium
解析：寻找最长的无重复字母的子字符串。
方法一：穷举遍历（★★★）
遍历所有的子字符串，判断其是否含有相同的字母，如果不包含相同的字母，且将result不断更新为最大的符合条件的子字符串的长度
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;
}
}
结果：Runtime: [Time Limit Exceeded]
备注：时间复杂度O(n^3)，显然这个操作很差。
方法二：Set筛选（★★★★）
取子串 [ i，j ]，子串中字符均在Set之中，取下一字符 s[ j+1 ]，如果Set不包含字符s[ j+1 ]，则取子串 [ i，j +1]，ans ++，继续取下一字符重复如上判断，如果Set包含字符s[ j+1 ]，则取子串 [ i+1，j ]，继续取字符 s[ j+1 ]重复如上判断，直至 j >= n 结束，ans 为最后的结果结果。
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;
}
}
结果：Runtime: 30 ms，beats 65.53% of Java submission.
备注：遍历数组，时间复杂度O(n)。
方法三：数组筛选（★★★★★）----所有用户提交通过的答案中的最佳方法之一
ASCII码，65 ~ 90代表[A，Z]，97~122代表[a，z]，数组index[]只需128位即可代表全部码值。
在数组index[]中，例如字符串“abcdefg”，其中“a”的ASCII码为97，位于字符串的第1位，故存于index[97] = 1，以此类推；
数字 i 记录的是字符最后一次出现的位置，当 i > 0时，i之前的子串必然会有和i重复的字符（ [0，i] 范围的子字符串的最大子串已保存于ans中），故只需考虑 i 之后的子串，即仅考虑 [i,j] 范围的子字符串，更新ans。
总而言之，即数字 i 记录每一次重复字符最新的位置，把原始字符串用 i 分为若干不重复的子字符串，用ans记录各个子字符串的大小。
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
int[] index = new int[128]; // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
i = Math.max(index[s.charAt(j)], i);
ans = Math.max(ans, j - i + 1);
index[s.charAt(j)] = j + 1;
}
return ans;
}
}
结果：Runtime: 16 ms.
备注：遍历数组，时间复杂度O(n)。
