剑指 Offer 48. 最长不含重复字符的子字符串
本问题对应的 leetcode 原文链接：剑指 Offer 48. 最长不含重复字符的子字符串
对应打卡任务：【动态规划专题】剑指 Offer 48. 最长不含重复字符的子字符串
问题描述
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示:
s.length <= 40000
解题思路
视频讲解直达： 本题视频讲解
代码实现
class Solution {
// public int lengthOfLongestSubstring(String s) {
// if(s == null || s.length() <= 0){
// return 0;
// }
// // 优化 => 单个变量
// Map<Character,Integer> map = new HashMap<>();
// int[] dp = new int[s.length()];
// dp[0] = 1;
// map.put(s.charAt(0), 0);
// int res = 1;
// for(int i = 1; i < s.length(); i++){
// if(!map.containsKey(s.charAt(i))){
// dp[i] = dp[i-1] + 1;
// }else{
// int k = map.get(s.charAt(i));
// dp[i] = i - k <= dp[i-1] ? i - k : dp[i-1] + 1;
// }
// res = Math.max(res, dp[i]);
// map.put(s.charAt(i), i);
// }
// return res;
// }
// 优化版本
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() <= 0){
return 0;
}
// 优化 => 单个变量
Map<Character,Integer> map = new HashMap<>();
//int[] dp = new int[s.length()];
int a = 1;
map.put(s.charAt(0), 0);
int res = 1;
for(int i = 1; i < s.length(); i++){
if(!map.containsKey(s.charAt(i))){
a = a + 1;// 就是没有刷新 a 之前，a表示dp[i-1]
}else{
int k = map.get(s.charAt(i));
a = i - k <= a ? i - k : a + 1;
}
res = Math.max(res, a);
map.put(s.charAt(i), i);
}
return res;
// 时间On,空间On
}
}
时间复杂度：O(n)
空间复杂度：O(n)