题解 | #最长不含重复字符的子字符串# 小白思路版

//本题用动态规划求解，第一次完完全全按照自己思路实现，记录一下

//  dp【n】设为以字符串第n个元素结尾的最长的子字符串
//  本题用hashMap<Character,Integer> 记录暂存的子字符串
//  dp[n]的求解思路  循环遍历字符串  

// 细分为 三种情况：

//一.当 第i个字符等于 第i-1 个字符时 --前面的字符串已经不能达到题目所给的要求，所以直接清除，长度置为1

//二、 当 第i个字符 不 等于 第i-1 个字符时，且map中不含该字符时，说明该字符在当前子字符串中无重复，直接加一
//方程：dp【i】 = dp【i-1】 + 1

//三、 当 第i个字符 不 等于 第i-1 个字符时，map中有该字符，即包含第i-1个字符的子字符串中 含有第i个元素
// 方程：dp【i】 = i- map.get(s.charAt(i));
//注意：以第i个字符结尾的情况中，可能以第i-1个字符结尾的子字符串也可能重复
//这个时候 方程： dp【i】应为 dp【i-1】 + 1
//综合两种情况，取最小值 ，因为小范围不成立大范围不可能成立


//状态转移方程代码如下：

import java.util.*;

public class Solution {
  
    public int lengthOfLongestSubstring(String s) {

        if (s.length() < 1){
            return 0;
        }else if (s.length() ==1){
            return 1;
        }
	  
	//  dp【n】设为以字符串第n个元素结尾的最长的子字符串
        int[] dp = new int[s.length()];
	  
	 //初始化
        dp[0] = 1;
	  
	 //暂存最大值dp【i】
        int temp = 0;
        int ans = 0;

	//hashMap<Character,Integer> 记录暂存的子字符串
        Map<Character,Integer> map  = new HashMap<>();
	  
	//初始化
        map.put(s.charAt(0),0);
        for (int i = 1; i < s.length(); i++) { //遍历字符串
		  
	//当 第i个字符等于 第i-1 个字符时 前面的字符串已经不能达到题目所给的要求，所以直接清除，长度置为1
	//然后以该字符开始新的子字符串
            if (s.charAt(i) == s.charAt(i-1)){ 
                map.clear();
                dp[i] = 1;
                map.put(s.charAt(i),i);
            }
		  
            else{
			  
	//当map中不含该字符时，说明该字符在当前子字符串中无重复，直接加一
	// dp【i】 = dp【i-1】 + 1
                if (!map.containsKey(s.charAt(i))) {
                    dp[i] = dp[i - 1] + 1;
                    map.put(s.charAt(i),i);
                }
			  
	//还有一种情况是map中有该字符，包含第i-1个字符的子字符串中含有第i个元素
	//dp【i】 = i- map.get(s.charAt(i));
	//注意：以第i个字符结尾的情况中，可能以第i-1个字符结尾的子字符串也可能重复
	//这个时候dp【i】应为 dp【i-1】 + 1
	//综合两种情况，取最小值
                else {
                    dp[i] = Math.min(i - map.get(s.charAt(i)),dp[i-1] + 1)  ;
                    map.replace(s.charAt(i),i);
                }
            }
            if (dp[i] > temp){
                temp = dp[i];
            }
        }

        ans = temp;
        return ans;
    }
}