Longest substring without repeated characters (Sword finger offer 48)

The longest substring without repeating characters ( The finger of the sword Offer 48)

1 Problem description

Please find the longest substring in the string that does not contain duplicate characters , Calculate the length of the longest substring .

 Input : "abcabcbb"
 Output : 3 
 explain :  Because the longest substring without repeating characters is  "abc", So its length is  3.

2 Their thinking

The length is N Shared string (n+1)n/2 The traversal complexity of the substring is O(n²), Judge the length as N The complexity of whether the string has duplicate characters is O(N) , Therefore, the complexity of using violence to solve this problem is O(n³).

First thought of using HashSet Reduce , Judge the length as N The complexity of whether the string has duplicate characters is O(1), towards set Add , return false There is repetition . So use double cycle plus HashSet The time complexity of solving the problem is O(n²).

thought ： The first layer iterates through the string , from s[i]( Starts 0) Start , Second layer circulating feed s[i+1] Began to set Add elements to it , If returns flase, Record the current set The size is the length of the non repeating substring , And empty set Exit the second loop , use sum preservation set The maximum size . Enter the next cycle from i+1 Start judging .

class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        if(s.equals("")||s==null){
    
            return 0;
        }
        int sum=0;
        Set<Character> set = new HashSet<>();
        for(int i = 0;i<s.length();i++){
    
            set.add(s.charAt(i));
            for(int j = i+1;j<s.length();j++){
    
                if(!set.add(s.charAt(j))){
    
                    sum=Math.max(sum,set.size());
                    set.clear();
                    break;
                }
            }
            sum=Math.max(sum,set.size());
        }
        return sum;
    }
}

3 improvement

The time complexity of using violence is too large , Therefore, we can consider using dynamic programming to reduce the time complexity . The main problem is to find the distance between two identical characters that are farthest apart , Consider using HashMap Save the subscript of each character , When traversing to the same character, the distance between them is saved and updated HashMap, Finally, return the maximum value of the distance saved each time .

State definition ： Set up a dynamic programming list dp ,dp[j] Represents with the character s[j] For the end of “ The longest non repeating substring ” The length of .

Transfer equation ： Fixed right border j , Set character s[j] The same character nearest to the left is s[i] , namely s[i] = s[i]=s[j] .

When i<0 , namely s[j] There is no same character on the left , be dp[j] = dp[j-1] + 1;
When dp[j−1]<j−i , Describe the previous and s[i] The same characters are not included in this time s[i] Substring of dp[j-1] in , be dp[j] = dp[j - 1] + 1 ;
When dp[j−1]≥j−i , Describe the previous and s[i] Want the same characters to contain s[i] Substring of dp[j−1] In the interval , be dp[j] The left boundary of is bounded by s[i] decision , namely dp[j] = j - i;

Finally back to max(dp).

Because the return value is dp List maximum , So with the help of variables tmp Storage dp[j] , Variable res Update the maximum value of each round .

class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        if(s.equals("")||s==null){
    
            return 0;
        }
        int temp = 0;
        int res = 0;
        HashMap<Character,Integer> map = new HashMap<>();
        for(int i = 0;i<s.length();i++){
    
            int j = map.getOrDefault(s.charAt(i),-1);
            map.put(s.charAt(i),i);
            if(temp<i-j){
    
                temp++;
            }else{
    
                temp = i-j;
            }
            res = Math.max(res,temp);
        }
        return res;
    }
}