day-25 无重复字符的最长子串

思路：动态规划的思想，遍历字符串，每遇到一个新的字符，将其存入HashMap中，并给其一个唯一值value(value递增)，当前字符若与HashMap中的字符都不一样，则存入HashMap中，若已经存在，则将对应value小于当前字符value的字符全部删除，最后返回dp数组的最大值即可

注意点：for循环遍历HashMap时，若调用remove函数，HashMap.会立即重排

code:

class Solution {

    public int lengthOfLongestSubstring(String s) {

        if(s.length()==0)return 0;
Map<Character,Integer> map=new HashMap<Character,Integer>();
int dp[]=new int[s.length()];
dp[0]=1;
int total=1;
map.put(s.charAt(0),1);
for(int i=1;i<s.length();i++){

     if(map.getOrDefault(s.charAt(i),-1)==-1){

        dp[i]=dp[i-1]+1;
        total++;
        map.put(s.charAt(i),total);
    }else{

      total=total+1;
      List<Character> list=new ArrayList<>();
      dp[i]=total-map.get(s.charAt(i));
     for(char ch:map.keySet()){

         if(map.get(ch)<map.get(s.charAt(i))){

             list.add(ch);
         }
     }
     for(int j=0;j<list.size();j++){

         map.remove(list.get(j));
     }
      map.put(s.charAt(i),total);
    } 
}
Arrays.sort(dp);
return dp[s.length()-1];
    }
}

原文链接: https://blog.csdn.net/qq_53568730/article/details/136922174

目录