The sword refers to offer 48: the longest non-repeating substring

Title description:

Please find the longest substring that does not contain repeated characters from the string, and calculate the length of the longest substring.

Example 1:

Enter: "abcabcbb"

Output: 3

Explanation: Since the longest substring without repeating characters is "abc", its length is 3.

Example 2:

Enter: "bbbbb"

Output: 1

Explanation: Since the longest substring without repeating characters is "b", its length is 1.

Example 3:

Enter: "pwwkew"

Output: 3

Explanation: Since the longest substring without repeating characters is "wke", its length is 3.
Please note that your answer must be the length of the substring, "pwke" is a subsequence, not a substring.

Solution 1: Sliding window

Ideas:

First, left and right point to the head of the window at the same time, and the right window keeps moving to the right. Use Set to maintain a non-repetitive sliding window. When encountering duplicate elements, immediately move the left window to remove duplicates, and record the window empty at this time.length.The previous steps are then repeated until the window has traversed all elements.

Code:

class Solution {public int lengthOfLongestSubstring(String s) {int res = 0;Set set = new HashSet<>();for(int l = 0, r = 0; r < s.length(); r++) {char c = s.charAt(r);while(set.contains(c)) {set.remove(s.charAt(l++));}set.add(c);res = Math.max(res, r - l + 1);}return res;}}

Solution 2: Double-ended queue

Ideas:

Use a double-ended queue as a sliding window. When encountering an existing number in the queue, delete it from the head of the queue (until the existing number is deleted), otherwise add elements from the end of the queue

Code:

class Solution {public int lengthOfLongestSubstring(String s) {Deque deque = new ArrayDeque<>();int max=0;for (int i = 0; i < s.length(); i++) {if (!deque.contains(s.charAt(i))) {deque.addLast(s.charAt(i));}else {max = Math.max(max, deque.size());while(deque.peekFirst()!=s.charAt(i)) {deque.removeFirst();}deque.removeFirst();deque.addLast(s.charAt(i));}}max = Math.max(max, deque.size());return max;}}