3. Longest Substring Without Repeating Characters
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.
3.不考虑重复字符的最长子串。
给一个字符串，找到长度最长的的子串，且子串中没有重复字符。
注意，答案必须是一个子串，"pwke"是一个子序列，但是不是一个子串。换句话说就是要连续。
解：
第一个思路，用一个变量记录最长子串长度，直接暴力从头到尾两层遍历，找出所有子串，每个子串中再用一个set计算是否存在重复字符，如果存在重复字符则跳过；否则记录最大子串长度。
这个思路很明显需要时间复杂度O(n2),且判断重复又需要n，大约需要O(n3)。所以，不考虑这种方案。
第二个思路，用一个变量记录最长子串长度，把这个set放到全局去，i,j两个变量作为子串的首尾，如果set没有j位置的字符，j++，把该字符加入set中，记录最长子串长度；如果存在，j不变，移除set中i位置的字符，i++，直到set中没有j的字符。
这种思路呢，最坏的情况，是例子中的第二个，i,j都遍历n次，最好的情况是没有重复字符，只需要遍历n。时间复杂度为O(n)。空间复杂的话，最坏情况下是没有重复字符，为O(n)。
以下为代码：
public int lengthOfLongestSubstring(String s) {
int n = s.length();
int ans = 0, i = 0, j = 0;
Set<Character> set = new HashSet<Character>();
while (i < n && j < n) {
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;
}
