_0003LongestSubstringWithoutRepeatingCharacters.java

package com.heatwave.leetcode.problems;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

/**
 * Given a string s, find the length of the longest substring without repeating characters.
 * <p>
 *  
 * <p>
 * Example 1:
 * <p>
 * Input: s = "abcabcbb"
 * Output: 3
 * Explanation: The answer is "abc", with the length of 3.
 * Example 2:
 * <p>
 * Input: s = "bbbbb"
 * Output: 1
 * Explanation: The answer is "b", with the length of 1.
 * Example 3:
 * <p>
 * Input: s = "pwwkew"
 * Output: 3
 * Explanation: The answer is "wke", with the length of 3.
 * Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.
 *  
 * <p>
 * Constraints:
 * <p>
 * 0 <= s.length <= 5 * 104
 * s consists of English letters, digits, symbols and spaces.
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class _0003LongestSubstringWithoutRepeatingCharacters {
    static class Solution {
        public int lengthOfLongestSubstring(String s) {
            int max = 0;
            Set<Character> characters = new HashSet<>();
            Deque<Character> deque = new ArrayDeque<>();

            for (int i = 0; i < s.length(); i++) {
                char c = s.charAt(i);
                if (characters.contains(c)) {
                    char firstChar;
                    do {
                        firstChar = deque.removeFirst();
                        characters.remove(firstChar);
                    } while (!deque.isEmpty() && firstChar != c);

                    characters.add(c);
                    deque.addLast(c);
                } else {
                    characters.add(c);
                    deque.addLast(c);

                    if (characters.size() > max) {
                        max = characters.size();
                    }
                }
            }

            return max;
        }
    }
}