03. Longest substring without repeated characters

#03. Longest substring without repeating characters

difficulty ： secondary

Given a string , Please find out that there are no duplicate characters in it Longest substrings The length of .

Example 1:

Input : s = "abcabcbb" Output : 3 explain : Because the longest substring without repeating characters is "abc", So its length is 3. Example 2:

Input : s = "bbbbb" Output : 1 explain : Because the longest substring without repeating characters is "b", So its length is 1. Example 3:

Input : s = "pwwkew" Output : 3 explain : Because the longest substring without repeating characters is "wke", So its length is 3. Please note that , Your answer must be Substring The length of ,"pwke" Is a subsequence , Not substring . Example 4:

Input : s = "" Output : 0

Tips ：

0 <= s.length <= 5 * 104 s By the English letters 、 Numbers 、 Symbols and spaces

# queue

# Ideas

If there is repetition, it will be directly thrown out of the queue

# Code

class Solution {
    public static int lengthOfLongestSubstring(String s) {
        Queue<Character> queue = new LinkedList<>();
        int length = 0;
        for (char c:s.toCharArray()){
            while (queue.contains(c)) {
                queue.poll();
            }
            queue.add(c);
            length = Math.max(length, queue.size());
        }
        return length;
    }
}

Copy

# Set Method

# Ideas

To judge whether or not to repeat , If repeated, repeat the elements from set Remove... From collection , obtain set.size

# Code

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int left = 0, right = 0, max = 0;
            Set<Character> set = new HashSet<>();
            while (right < s.length()) {
                if (set.contains(s.charAt(right))) {
                    set.remove(s.charAt(left++));
                } else {
                    set.add(s.charAt(right++));
                    max = Math.max(max, set.size());
                }
            }
            return max;
    }
}

Copy