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.

题意

给你一个字符串，返回没有重复字符的最长子串的长度。

思路

使用一个 Set 存放当前的候选最长子串（没必要顺序存储）。遍历字符串，在将当前遍历的字符存入候选最长子串之前。如果子串中，存在当前遍历的字符，即构成重复子串，则按顺序将字符一个一个地从候选子串移除，直到重复字符被移出为止。

由于 Set 无序的特性，如何知道接下来该移除哪个字符呢？我们可以维护一个索引（byeIndex），该索引记录了候选子串中的第一个字符，即接下来该移除的字符。

代码

package name.guolanren._1to100._1to10.p3;

import java.util.HashSet;
import java.util.Set;

/**
 * @author guolanren
 */
public class LongestSubstringWithoutRepeatingCharacters {

    public int lengthOfLongestSubstring(String s) {
        int maxLength = 0;
        int byeIndex = 0;
        // 乱序的候选最长字符串
        Set<Character> candidate = new HashSet<>();
        for (int i = 0; i < s.length(); i++) {
            // 已经追不上啦，放弃吧
            if (s.length() - i + candidate.size() <= maxLength) {
                break;
            }
            char c = s.charAt(i);
            // 遇到重复的，按顺序删除，直到跟相同的字符说 bye 为止
            while (candidate.contains(c)) {
                char bye = s.charAt(byeIndex++);
                candidate.remove(bye);
            }
            candidate.add(c);
            maxLength = Integer.max(maxLength, candidate.size());
        }
        return maxLength;
    }

}