剑指 Offer 48. 最长不含重复字符的子字符串
本问题对应的 leetcode 原文链接：剑指 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)
Python
class Solution(object):
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
if not s:
return 0
map = {}
a = 1
map[s[0]] = 0
res = 1
for i in range(1, len(s)):
if s[i] not in map:
a += 1
else:
k = map[s[i]]
a = i - k if i - k <= a else a + 1
res = max(res, a)
map[s[i]] = i
return res
C++
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.empty()) {
return 0;
}
unordered_map<char, int> mp;
int a = 1;
mp[s[0]] = 0;
int res = 1;
for(int i = 1; i < s.length(); ++i) {
if(mp.find(s[i]) == mp.end()) {
++a;
} else {
int k = mp[s[i]];
a = (i - k <= a) ? (i - k) : (a + 1);
}
res = max(res, a);
mp[s[i]] = i;
}
return res;
}
};
Go
func lengthOfLongestSubstring(s string) int {
if len(s) == 0 {
return 0
}
m := make(map[byte]int)
a := 1
m[s[0]] = 0
res := 1
for i := 1; i < len(s); i++ {
if _, ok := m[s[i]]; !ok {
a += 1
} else {
k := m[s[i]]
if i-k <= a {
a = i - k
} else {
a += 1
}
}
if a > res {
res = a
}
m[s[i]] = i
}
return res
}
JS
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
if (s == null || s.length <= 0) {
return 0;
}
// 优化 => 单个变量
let map = new Map();
//let dp = new Array(s.length).fill(0);
let a = 1;
map.set(s.charAt(0), 0);
let res = 1;
for (let i = 1; i < s.length; i++) {
if (!map.has(s.charAt(i))) {
a = a + 1; // 就是没有刷新 a 之前，a表示dp[i-1]
} else {
let k = map.get(s.charAt(i));
a = i - k <= a ? i - k : a + 1;
}
res = Math.max(res, a);
map.set(s.charAt(i), i);
}
return res;
};