Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.
Example 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.
public int lengthOfLongestSubstring(String s) {
if (s == null) {
return 0;
}
int max = 0;
Set<Character> set = new HashSet<>();
int i = 0;
int startIndex = 0; // 回溯的位置,这里要小心，每次回溯的位置应该是上一个子链开始的后一个位置，如果忽略这个事实，回溯就会出错。
while (i < s.length()) {
Character c = s.charAt(i);
if (!set.contains(c)) {
set.add(c);
} else {
max = set.size() > max ? set.size() : max;
set.clear();
i = startIndex + 1;
startIndex = i;
continue;
}
++ i;
}
if (!set.isEmpty()) {
max = set.size() > max ? set.size() : max;
}
return max;
}
小结: 本质是找最长不重复子串，一开始感觉还挺简单，就开始写了，写完后提交检验出不对。解决此题用了回溯法，但是一开始只是顺次读取，回溯的地方没有找对，因此出错。还是应该应该将情况考虑全面。
