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

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。

提示：

• s.length <= 40000

题解一：

动态规划解析：

• 状态定义： 设动态规划列表 dp，dp[j] 代表以字符 s[j] 为结尾的 “最长不重复子字符串” 的长度

• 转移方程：固定右边界 j，设字符 s[j] 左边距离最近的相同字符为 s[i]，即 s[i] = s[j]

  1. 当 i < 0，即 s[j] 左边无相同字符，则 dp[j] = dp[j-1] + 1
  2. 当 dp[j-1] < j - i，说明字符 s[i] 在子字符串 dp[j-1] 区间之外 ，则 dp[j] = dp[j - 1] + 1
  3. 当 dp[j−1] ≥ j − i，说明字符 s[i] 在子字符串 dp[j-1]区间之中 ，则 dp[j] 的左边界由 s[i] 决定，即 dp[j] = j - i

• 返回值：max(dp) ，即全局的 “最长不重复子字符串” 的长度。

	/**
     * 剑指 Offer 48. 最长不含重复字符的子字符串
     */
    public int lengthOfLongestSubstring(String s) {
        // 存储各字符最后一次出现的下标
        Map<Character, Integer> map = new HashMap<>();
        int res = 0;
        int tmp = 0;

        for (int j = 0; j < s.length(); j++) {
            // 获取当前字符的索引
            int i = map.getOrDefault(s.charAt(j), -1);
            map.put(s.charAt(j), j);
            // dp[j - 1] -> dp[j]
            tmp = tmp < j - i ? tmp + 1 : j - i; 
            // max(dp[j - 1], dp[j])
            res = Math.max(res, tmp); 
        }

        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

题解二：

	/**
     * 剑指 Offer 48. 最长不含重复字符的子字符串
     */
    public int lengthOfLongestSubstring(String s) {
        int res = 0;
        int tmp = 0;

        for(int j = 0; j < s.length(); j++) {
            int i = j - 1;
            // 线性查找 i
            while(i >= 0 && s.charAt(i) != s.charAt(j)) {
                i--; 
            }
            // dp[j - 1] -> dp[j]
            tmp = tmp < j - i ? tmp + 1 : j - i; 
             // max(dp[j - 1], dp[j])
            res = Math.max(res, tmp);
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

题解三：

	/**
     * 剑指 Offer 48. 最长不含重复字符的子字符串
     */
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int i = -1, res = 0;
        
        for(int j = 0; j < s.length(); j++) {
            if(dic.containsKey(s.charAt(j))) {
                // 更新左指针 i
                i = Math.max(i, dic.get(s.charAt(j))); 
            }
            dic.put(s.charAt(j), j); 
            // 更新结果
            res = Math.max(res, j - i); 
        }
        return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof