力扣--LCR 167.招式拆解I

题目

某套连招动作记作序列 arr，其中 arr[i] 为第 i 个招式的名字。请返回 arr 中最多可以出连续不重复的多少个招式。

示例 1：

输入：arr = “dbascDdad”
输出：6
解释：因为连续且最长的招式序列是 “dbascD” 或 “bascDd”，所以其长度为 6。

示例 2：

输入：arr = “KKK”
输出：1
解释：因为无重复字符的最长子串是 “K”，所以其长度为 1。

示例 3：

输入：arr = “pwwkew”
输出：3
解释：因为连续且最长的招式序列是 “wke”，所以其长度为 3。
请注意区分 子串 与 子序列 的概念：你的答案必须是 连续招式 的长度，也就是 子串。而 “pwke” 是一个非连续的 子序列，不是 子串。

提示：

0 <= arr.length <= 40000
arr 由英文字母、数字、符号和空格组成。

代码

class Solution {
// public int lengthOfLongestSubstring(String s) {
// if(s == null || s.length() <= 0){
// return 0;
// }
// // 优化 => 单个变量
// Map<Character,Integer> map = new HashMap<>();
// int[] dp = new int[s.length()];
// dp[0] = 1;
// map.put(s.charAt(0), 0);
// int res = 1;
// for(int i = 1; i < s.length(); i++){
// if(!map.containsKey(s.charAt(i))){
// dp[i] = dp[i-1] + 1;
// }else{
// int k = map.get(s.charAt(i));
// dp[i] = i - k <= dp[i-1] ? i - k : dp[i-1] + 1;
// }
// res = Math.max(res, dp[i]);
// map.put(s.charAt(i), i);
// }

//     return res;
// }

// 优化版本
public int lengthOfLongestSubstring(String s) {
    if(s == null || s.length() <= 0){
        return 0;
    }
    // 优化 => 单个变量
    Map<Character,Integer> map = new HashMap<>();
    //int[] dp = new int[s.length()];
    int a = 1;
    map.put(s.charAt(0), 0);
    int res = 1;
    for(int i = 1; i < s.length(); i++){
        if(!map.containsKey(s.charAt(i))){
            a = a + 1;// 就是没有刷新 a 之前，a表示dp[i-1]
        }else{
            int k = map.get(s.charAt(i));
            a = i - k <= a ? i - k : a + 1;
        }
        res = Math.max(res, a);
        map.put(s.charAt(i), i);
    }

    return res;
    // 时间On,空间On
}

}