[sword finger offer] 48 Longest substring without duplicate characters

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

subject

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

Ideas

• Set the status array 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[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, Description character s[i] In substring dp[j - 1] Out of range , be dp[j] = dp[j - 1] + 1; When dp[j - 1] >= j - i, Description character s[i] In string dp[j - 1] Within the interval , be dp[j] The left boundary of is bounded by s[i] decision , namely dp[j] = j - i;

• return max(dp)

Code

class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        Map<Character,Integer> dic = new HashMap<>();//  Define a hash table 
        int res = 0,tmp = 0;

        for(int j = 0; j < s.length(); j++)
        {
    
            int i = dic.getOrDefault(s.charAt(j),-1);// s.charAt(j) Gets the character of the current position , Then look up the position of the last occurrence of the character from the hash table 
            //  Store the character position in the hash table 
            dic.put(s.charAt(j),j);//  Update hash table 

            //  Calculate the difference between the current position and the last position   and tmp（tmp Is the longest substring length of the previous character ） Compare 
            //  Here, the longest substring length of the current character is updated 
            if(tmp < j -i)
            {
    
                tmp = tmp + 1;
            }
            else
            {
    
                tmp = j - i;
            }
            //  to update res
            res = Math.max(res,tmp);// max(dp[j - 1],dp[j])
        }
        return res;
    
    }
}