This is the 15th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021 “@TOC

The title information

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

Example 1:

Enter: s ="abcabcbb"Output:3Because the oldest string without repeating characters is"abc", so its length is3.Copy the code

Example 2:

Enter: s ="bbbbb"Output:1Because the oldest string without repeating characters is"b", so its length is1.Copy the code

Example 3:

Enter: s ="pwwkew"Output:3Because the oldest string without repeating characters is"wke", so its length is3. Please note that your answer must be the length of the substring,"pwke"It's a subsequence, not a substring.Copy the code

Example 4:

Enter: s =""Output:0
Copy the code

Double pointer scanning

Assume that the following string is the string given by the problem.

Define the result res to represent the length of the oldest string. Define double Pointers I and j both at first0Index position, traverse the entire string, and then define the hash tablemap, the key-value pair is Character,Integer. Represents the number of occurrences of the current character. Every time you encounter a character, put it inmapUntil the character is inmapThe value of value in1, which indicates the existence of duplicate characters. Then put the current j subscript character inmap, value is the value of the current j subscript minus1; Then j++; Update the res. Finally, return res.Copy the code

Implementation code:

    public int lengthOfLongestSubstring(String s) {
        HashMap<Character,Integer> hashMap=new HashMap<> ();
        int res=0;
        for(int i=0, j=0; i<s.length (); i++){ hashMap.put (s.charAt (i), hashMap.getOrDefault (s.charAt (i),0) +1);
            while (hashMap.get (s.charAt (i))>1){
                hashMap.put (s.charAt (j), hashMap.get (s.charAt (j))-1);
                j++;
            }
            res=Math.max (res,i-j+1);
        }
        return  res;
    }
Copy the code