This is the seventh day of my participation in the August More text Challenge. For details, see: August More Text Challenge

3. The oldest string with no duplicate characters

Given a string, find the longest string that does not contain repeating characters. Example 1:

Input:"abcabcbb"Output:3Explanation: Because the most common string with no duplicate characters is"abc", so its length is zero3.Copy the code

Example 2:

Input:"bbbbb"Output:1Explanation: Because the most common string with no duplicate characters is"b", so its length is zero1.Copy the code

Example 3:

Input:"pwwkew"Output:3Explanation: Because the most common string with no duplicate characters is"wke", so its length is zero3. Note that your answer must be the length of the substring,"pwke"It's a subsequence, not a substring.Copy the code

Completion code:

class Solution {
    public int lengthOfLongestSubstring(String s) {}}Copy the code

When we look at the problem, as usual, whether it’s going to happen or not, we’re going to add the necessary initialization and return values.

int num = 0;
//TODO
return num;
Copy the code

The first thought I had when I saw this problem was to take all the non-repeating string number segments and compare each large size to the largest one. Such as:

"abcabcbb"

"adc"
"bca"
"cab"
"abc"
"bc"
"cb"
"b"
"b"
Copy the code

So it’s 3. All right, let’s get on the code.

public static int lengthOfLongestSubstring(String s) {
    int num = 0;
    // Used to store strings
    HashSet<Character> hashSet;
    // Loop from the beginning to the end
    for (int i = 0; i < s.length(); i++) {
        hashSet = new HashSet<>();
        // Loop from I at a time
        for (int j = i; j < s.length(); j++) {
            // Exit if it exists
            if (hashSet.contains(s.charAt(j))) {
                break;
            }
            // No additions exist
            hashSet.add(s.charAt(j));
            // Determine the size of the set
            if(num < hashSet.size()) { num = hashSet.size(); }}}return num;
}
Copy the code

As expected, the efficiency. Hahaha, it’s not great, but it works. Let’s start with a little bit of optimization.

To optimize the

We can list each one, we just list all the fields that are not repeated, such as

"abcabcbb"

"adc"
// Kick out a and before a
"bca"
// When b is encountered, kick out b and before B
"cab"Kick out c and before C"abc"When it comes to B it kicks out B and before B"cb"When a kicks out B and before B"b"
Copy the code

There are two fewer results. This is done in code.

public static int lengthOfLongestSubstring(String s) {
    int num = 0;
    // Select the element from which the record is removed
    int count = 0;
    HashSet<Character> hashSet = new HashSet<>();
    for (int i = 0; i < s.length(); i++) {
        // If the set contains
        while (hashSet.contains(s.charAt(i))) {
            hashSet.remove(s.charAt(count));
            count++;
        }
        // Add new elements
        hashSet.add(s.charAt(i));
        // Determine the size of the set
        if(num < hashSet.size()) { num = hashSet.size(); }}return num;
}
Copy the code

Yeah, yeah, yeah, yeah, yeah. Ha ha. It only beat more than 50% of users, but I have a feeling they were written in c++. (Give yourself a little excuse)