The title

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

Example:

  • Given “abcabcbb”, the oldest string without repeating characters is “ABC”, then the length is 3.

  • Given “BBBBB”, the longest substring is “b” with length 1.

  • Given “pwwkew”, the oldest string is “wke” and has length 3. Note that the answer must be a substring; “pwke” is a subsequence, not a substring.

Plan 1

Ideas:

  • The number corresponding to the character is used as the subscript

  • Initialize a Boolean of 255 as the possibility for all possible characters, false if there are no duplicates, true if there are duplicates.

  • Two Pointers are moved, the first pointer is not moved, and the second pointer is moved and is judged by whether the integer subscript corresponding to the current character is false or true. If false, there is no duplication and the pointer moves back one bit; If true, the back pointer stops moving, the current string length is calculated, and the Boolean array is reset so that the first pointer is moved one bit forward and the back pointer points to the current front pointer.

class Solution {
    public int lengthOfLongestSubstring(String s) {
         int len = 0 ;

        if (s==null || s.length()== 0 )
        {
            return 0;
        }
        if (s.length() == 1){

            return 1;
        }

        int firstPoint = 0;
        int nextPoint = 0;

        boolean[] exist=new boolean[255];

        while (nextPoint < s.length()&&firstPoint <s.length()){

            int currMax = 0;
            int index = s.charAt(nextPoint)-0;
            while (exist[index] == false&&nextPoint<s.length()){
                exist[s.charAt(nextPoint)-0] = true;
                nextPoint++;
                if (nextPoint < s.length()){
                    index = s.charAt(nextPoint)-0;
                }

            }

            currMax = Math.max(currMax,nextPoint-firstPoint);
            firstPoint++;
            nextPoint=firstPoint;
            len = Math.max(len,currMax);
            for (int i = 0 ; i < 255 ; i++)
            {
                exist[i] = false; }}returnlen; }}Copy the code

Scheme 2

Ideas:

First set a header pointer to the beginning of the string, then iterate over the string from the beginning. If the map does not contain the character, subtract the position of the header pointer from its current position. Then compare it to the maximum length, select the character to become the maximum length, and put the current character and position into map. Take abba as an example, the head pointer points to A, the current is A, so the length is 1, map. Put (‘b’,1), if the current character exists in the map, then the head pointer points to the larger of the current head pointer position and the next position in the map where the character position is stored. For example, when the second B is reached, Put (‘b’,2), then go to a, then the position of a in the current map is 0. So its next position is 1, compared to the current position of the head pointer 2, less than the current position of the head pointer, then the head pointer is not new, so the length is 2, equal to the maximum length, so it is not replaced, and finally the maximum length is 2.

public static int lengthOfLongestSubstring(String s) {  
        Map<Character,Integer> map=new HashMap<Character,Integer>();  
        int maxLength=0;  
        int now=0;  
        for(int i=0; i<s.length(); i++){if(map.containsKey(s.charAt(i))){  
                now=Math.max(map.get(s.charAt(i))+1,now);  
                if((i-now+1)>maxLength){ maxLength=i-now+1; }}else{  
                if((i-now+1)>maxLength){  
                    maxLength=i-now+1;  
                }  
            }  
            map.put(s.charAt(i), i);  
        }  
        return maxLength;  
    }  
Copy the code