48.最长不含重复字符的子字符串

raylan.chen大约 2 分钟

本来想着使用动态规划的，但是做着做着，好像有点脱离动态规划了...

时间复杂度有点高，貌似 $O(n^2)$

class Solution {
    public int dismantlingAction(String arr) {
        if (arr == null || arr.length() == 0) return 0;
        char[] chars = arr.toCharArray();
        int[] dp = new int[arr.length()];
        // 可以改成 Arrays.fill(dp, 1);
        for (int i = 0; i < arr.length(); i++) {
            // dp[] 记录当前元素的最长不含重复字符的子字符串长度
            dp[i] = 1;
        }
        // 每个字符本身算1
        int max = 1;
        //遍历字符数组
        for (int i = 1; i < chars.length; i++) {
            // tmp 为向前移动的次数(与前面的元素比较是否相同)，默认向左移动一格(即最少与前一个元素作比较)
            // 若 dp 数组中记录的数值大于1，则再向左挪动
            int tmp = 1;
            while (tmp <= dp[i - 1]) {
                //       d, v, d, f
                // dp[i] 1, 2, 2, 3
                // tmp   1, 2, 2, 3
                if (chars[i] == chars[i - tmp]) break;
                tmp++;
            }
            dp[i] = tmp;
            if (dp[i] > max) max = dp[i];
        }
        return max;
    }
}

优秀题解

class Solution {
    public int dismantlingAction(String arr) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0, len = arr.length();
        for(int j = 0; j < len; j++) {
            int i = dic.getOrDefault(arr.charAt(j), -1); // 获取索引 i
            dic.put(arr.charAt(j), j); // 更新哈希表
            tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
            res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
        }
        return res;
    }
}

作者：Krahets
链接：https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solutions/210129/mian-shi-ti-48-zui-chang-bu-han-zhong-fu-zi-fu-d-9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这才是真正的动态规划，时间复杂度 O(n)

dp[i] 代表以字符 arr[i] 结尾的最长不重复的连续子字符串

拿哈希表存储相同字符最后一次出现的索引

随后计算相同字符两者的间距与 dp[i - 1] 做对比，看前一个元素是否与哈希表中存储的相同字符做联结(组成最长不重复的连续子字符串)

若没有联结则 dp[i] = dp[i - 1] + 1（哈希表中没有存在相同字符也包括在内）

有联结则使用索引间距赋值

48.最长不含重复字符的子字符串

48.最长不含重复字符的子字符串

参考链接

个人尝试

优秀题解