[※ leetcode refers to offer 48. The longest substring without repeated characters (medium)]

subject ：

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

Example 1:

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

Input : “bbbbb”
Output : 1
explain : Because the longest substring without repeating characters is “b”, So its length is 1.
Example 3:

Input : “pwwkew”
Output : 3
explain : Because the longest substring without repeating characters is “wke”, So its length is 3.
Please note that , Your answer must be Substring The length of ,“pwke” Is a subsequence , Not substring .

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The problem solving process ：

Classical dynamic programming solution

import java.util.Hashtable;

class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        Map<Character, Integer> dict = new HashMap<>();
        int max = 1;
        int dp[] = new int[s.length()+1];  //  Always maintain the maximum length without duplicate characters 
        if(s.equals(""))
            return 0;
        dict.put(s.charAt(0),0);
        dp[0] = 1;
        for(int i = 1; i < s.length(); i++) {
    
            //  No repetition 
            if(!dict.containsKey(s.charAt(i))){
    
                dp[i] = dp[i-1]+1;
            }
            //  Duplicate occurs 
            else{
    
                //  Gets the position of the duplicate character in the atomic string 
                int repeat = dict.get(s.charAt(i)); 
                if(i-repeat>dp[i-1])
                    dp[i] = dp[i-1]+1;
                else
                    dp[i] = i-repeat;
            }
            //  Update the latest element location 
            dict.put(s.charAt(i),i);
            max = max>dp[i]?max:dp[i];
        }
        return max;
    }
}

Execution results ：