LeetCode剑指Offer48.寻找最长无重复字符子串（中等难度）

问题描述：

目标是从一个给定的字符串中找到最长的不包含重复字符的子串，并计算这个子串的长度。

示例 1:

输入: "abcabcbb"
输出: 3
说明: 因为无重复字符的最长子串是 "abc"，其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
说明: 因为无重复字符的最长子串是 "b"，其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
说明: 因为无重复字符的最长子串是 "wke"，其长度为 3。请注意，您的答案必须是子串的长度，"pwke" 是一个子序列，而非子串。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof
版权归力扣网络所有。商业用途需获得官方授权，非商业用途请注明出处。

解决方案：

使用动态规划方法解决此问题，通过哈希表记录字符最近出现的位置，从而高效地更新当前最长无重复字符子串的长度。

import java.util.HashMap; public class Solution { public int lengthOfLongestSubstring(String s) { HashMap map = new HashMap<>(); int maxLength = 0; int[] dp = new int[s.length() + 1]; if (s.isEmpty()) return 0; map.put(s.charAt(0), 0); dp[0] = 1; for (int i = 1; i  dp[i - 1]) { dp[i] = dp[i - 1] + 1; } else { dp[i] = i - lastOccurrence; } } map.put(s.charAt(i), i); maxLength = Math.max(maxLength, dp[i]); } return maxLength; } }

测试结果：