算法3. Longest Substring Without Repeating Characters

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(n²),且判断重复又需要n，大约需要O(n³)。所以，不考虑这种方案。

第二个思路，用一个变量记录最长子串长度，把这个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;
}