剑指Offer系列（java版，详细解析）48.最长不含重复字符的子字符串

小鱼儿 2023-01-13 09:35 119阅读 0赞

# 题目描述 #

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

难度中等187收藏分享切换为英文接收动态反馈

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

**示例 1:**

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

**示例 2:**

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

**示例 3:**

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

提示：

*  `s.length <= 40000`

# 测试用例 #

*  功能测试（包含多个字符的字符串；只要一个字符的字符串；所有都唯一的字符串；所有字符都相同的字符串）
 *  特殊输入测试（空字符串）

# 题目考点 #

*  考察应聘者用动态规划分析问题的能力。
 *  考察应聘者对递归及时间效率的理解。

# 解题思路 #

定义函数f(i)表示以第i个字符结尾的不包含重复字符的子字符串的最长长度。它有以下几种情况：

1.  如果第i个字符之前没有出现过 或者 出现的下标不在当前不包含重复字符的子字符串内：那么f(i) = f(i-1) + 1
2.  如果第i个字符出现的下标在当前不包含重复字符的子字符串内：则需要比较当前不包含重复字符的子字符串的长度与之前最长的不包含重复字符的子字符串谁比较长，如果比之前的长，那么需要调整之前最长的字符串的长度, 不管怎样，这时f(i) = d(两个重复字符串的距离)

# 自己解题 #

class Solution { 
        public int lengthOfLongestSubstring(String s) { 
            Map<Character, Integer> dic = new HashMap<>();
            int res = 0, tmp = 0;
            for(int j = 0; j < s.length(); j++) { 
                int i = dic.getOrDefault(s.charAt(j), -1); // 获取索引 i
                dic.put(s.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;
        }
    }

[Offer 48.]: https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/