剑指 Offer 48. 最长不含重复字符的子字符串 -- DP解法

LeetCode： 剑指 Offer 48. 最长不含重复字符的子字符串

与 滑动窗口 类似 >> 间接维护了一个不重复的元素的范围的最左边的位置

DP >> 转移方程 >> 对上一个区间长度 与 当前区间长度 去 min

最终结果 >> 通过一个 ans 变量记录

1. 状态定义： dp[j] 表示右边界下标为 j 的时候，可以取到的最长不重复范围长度。
2. 转移方程：

j - i 为一个区间 （当前下标 - 上一个重复元素的下标）
dp[j - 1] 上一个状态时最长的区间长度
dp[j] 当前状态的最长区间长度

当 j - i 这个区间没有出现重复元素时，j - i >> map.get(i) == null >> i 所以 i = -1, j - i 会比 dp[j - 1] 大 1
所以当前dp[j] 状态在上一个状态 + 1

当 j - 1 这个区间出现了重复元素 >> j - i 会小于等于上一个 dp[j - 1] 的区间长度 >> 所以当前状态 dp[j] 的区间长度更新为 j - i

即
当前状态 = 上一个状态 + 1 与 j - i 中 取 min

    public int mydp(String s){
        if("".equals(s) || s.length() == 0) return 0;
        // dp 数组  >>  可以通过一个变量 temp 来代替dp数组进行记录当前的区间长度
        int[] dp = new int[s.length()];
        Map<Character, Integer> map = new HashMap<>();
        // s = "d"
        int ans = 1;
        // 初始化
        dp[0] = 1;  
        map.put(s.charAt(0), 0);

        // 遍历数组
        for (int i = 1; i < s.length(); i++) {
            int j = map.getOrDefault(s.charAt(i), -1);
            map.put(s.charAt(i), i);
            // i - j  >>  当前下标减去上一个重复的下标
            dp[i] = dp[i - 1] < i - j ? dp[i - 1] + 1: i - j;
			
            ans = Math.max(dp[i], ans);
        }

        return ans;
    }

---

>> 解题思路