#3无重复字符的最长子串

import java.util.HashMap;
import java.util.Map;

final class Solution {
    public int lengthOfLongestSubstring(String s) {
        // 窗口不变量：收缩结束后，每个字符至多出现一次。
        // 右端字符重复时只需移出到其频次恢复为 1，随后才能更新答案。
        Map<Character, Integer> frequency = new HashMap<>();
        int left = 0;
        int answer = 0;
        for (int right = 0; right < s.length(); right++) {
            char added = s.charAt(right);
            frequency.merge(added, 1, Integer::sum);
            while (frequency.get(added) > 1) {
                char removed = s.charAt(left++);
                frequency.put(removed, frequency.get(removed) - 1);
            }
            answer = Math.max(answer, right - left + 1);
        }
        return answer;
    }
}