“This is my 27th day of participating in the First Challenge 2022. For more details: First Challenge 2022.”

A, the title

The difficulty of medium

Given a string, find the length of the smallest string that does not contain repeating characters.

Example 1:

Input: s = “abcabcbb” Output: 3 Explanation: Since the oldest string without repeating characters is “ABC”, its length is 3.

Example 2:

Input: s = “BBBBB” Output: 1 Explanation: Since the oldest string without repeating characters is “b”, its length is 1.

Example 3:

Input: s = “pwwkew” Output: 3 Explanation: Since the oldest string without repeating characters is “wKE”, its length is 3. Note that your answer must be the length of the substring, “pwke” is a * subsequence, * is not a substring.

Example 4:

Input: s = “output: 0

Tip:

• 0 <= s.length <= 5 * 104

• S consists of letters, digits, symbols, and Spaces

Second, my solution

First answer:

My idea is pretty much the same as the official one: start the cursor at the first and look for the longest

It’s just that I’m readding everything every time I delete the first one, instead of his concept of window movement

public static int lengthOfLongestSubstring(String s) { int selection = 0; int maxSize=0; while (selection < s.length()) { HashMap map = new HashMap<>(); List mapList = new ArrayList<>(); for (int i = selection; i < s.length(); i++) { char val = s.charAt(i); if (! map.containsKey(val)) { map.put(val, val); mapList.add(val); } else { break; } } maxSize=Math.max(mapList.size(),maxSize); selection++; if (mapList.size() >= (s.length() - selection)) { break; } } return maxSize; }Copy the code

By:

Three, system solution

Method 1: Sliding Windows

Ideas and Algorithms

Let’s start with an example of how we can get through this problem in optimal time complexity.

Using the string abcabcbb in example 1, find the longest string that does not contain repeating characters, starting with each character. For the string in example 1, we list these results, with parentheses indicating the selected character and the longest string:

The longest string beginning with (a)bcabcbb is (ABC)abcbb;

The longest string starting with a(b)cabcbb is a(bca) BCBB;

The longest string starting with ab(c)abcbb is ab(CAB) CBB.

The longest string starting with ABC (a) BCBB is ABC (ABC)bb;

The longest string starting with abca(b) CBB is abca(BC)bb.

The longest string starting with abcab(c)bb is abcab(cb)b.

The longest string starting with abcabc(b)b is abcabc(b)b;

The longest string starting with abcabcb(b) is abcabcb(b).

What was found? If we incrementally enumerate the start of the substring, then the end of the substring is also incrementally! The reason for this is that suppose we choose the KTH character in the string as the starting position and get the oldest string that does not contain repeating characters ending at position r_k. So when we choose the k+1 character as the starting position, the first character from k+1 to r_k is obviously not repeated, and since the original KTH character is missing, we can try to increase r_k until the repeated character appears on the right.

In this case, we can use “sliding Windows” to solve the problem:

We use two Pointers to represent the left and right boundaries of a substring (or window) in the string. The left pointer represents the “start of enumeration substring” above, and the right pointer is r_k above.

At each step, we move the left pointer one space to the right to indicate that we begin enumerating the next character as the starting position, and then we can keep moving the right pointer to the right, making sure that there are no duplicate characters in the substring corresponding to the two Pointers. At the end of the move, the substring corresponds to the oldest string that does not contain repeating characters, starting with the left pointer. We record the length of this substring;

At the end of the enumeration, the length of the longest substring we find is the answer.

Judge repeated character

In the above flow, we also need to use a data structure to determine if there are duplicate characters. Common data structures are hash sets (STD ::unordered_set in C++, HashSet in Java, Set in Python, set in JavaScript). When the left pointer moves to the right, we remove a character from the hash set, and when the right pointer moves to the right, we add a character to the hash set.

So we’ve solved our problem perfectly.

Note: the idea is the same as me, the code is much simpler than what I wrote

Class Solution {public int lengthOfLongestSubstring(String s) { Set<Character> ocC = new HashSet<Character>(); int n = s.length(); Int rk = -1, ans = 0; rk = -1; ans = 0; for (int i = 0; i < n; ++i) { if (i ! Occ.remove (s.charat (i-1)); // occ.remove(s.charat (i-1)); } while (rk +1<n &&!) {rk+1<n &&! Occ. contains(s.charat (rk + 1))) {// constantly moving the right pointer occ.add(s.charat (rk + 1)); ++rk; } // the i-rk character is an extremely long non-repeating character substring ans = math.max (ans, rk - I + 1); } return ans; }}Copy the code

Complexity analysis

• Time complexity: O(N), where N is the length of the string. Left and right Pointers traverse the entire string once each.

• Space complexity: O(∣ σ ∣) where σ represents the character set (that is, the characters that can appear in a string) and ∣ σ ∣ the size of the character set. In this case, the character set is not specified, so we can default to all ASCII characters within [0,128], that is, ∣ σ ∣=128. We need to use the hash set to store the characters that occur, and there are at most ∣ σ ∣, so the space complexity is O(∣ σ ∣).

This netizen is wonderful

Class Solution {public int lengthOfLongestSubstring(String s) {last = new int[128]; for(int i = 0; i < 128; i++) { last[i] = -1; } int n = s.length(); int res = 0; int start = 0; For (int I = 0; i < n; i++) { int index = s.charAt(i); start = Math.max(start, last[index] + 1); res = Math.max(res, i - start + 1); last[index] = i; } return res; }}Copy the code

One drawback of the answer is that the left pointer does not need to be incremented, which means there are many unnecessary loops. When a duplicate character is found, you can move the left pointer to the position next to the first duplicate character.

Each time the left pointer moves one bit to the right, it removes a character from the set, which leads to many useless loops. The repeated characters found by the while loop are not necessarily the same ones that were first added to the Set. It takes several loops to reach them. These are invalid loops, so it is better to use a map to record the index of each character and jump directly