var lengthOfLongestSubstring = function(s) {
let obj = {};
let left = 0, right = 0;
let maxLen = 0, maxStr = '';
while (right < s.length) {
let c = s[right];
right++;
if (obj[c]) obj[c]++;
else obj[c] = 1
while (obj[c] > 1) {
let d = s[left];
left++;
obj[d]--;
}
if (maxLen < right - left) {
maxLen = right - left;
}
}
return maxLen;
};
容易理解版本 (滑动窗口)
var lengthOfLongestSubstring = function(s) {
// 哈希集合,记录每个字符是否出现过
const occ = new Set();
const n = s.length;
// 右指针,初始值为 -1,相当于我们在字符串的左边界的左侧,还没有开始移动
let rk = -1, ans = 0;
for (let i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格,移除一个字符
occ.delete(s.charAt(i - 1));
}
while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {
// 不断地移动右指针
occ.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
};
最优解
function lengthOfLongestSubstring( s) {
let index = new Array(128);
let len = 0;
let length = s.length();
for (int i = 0, j = 0; j < length; j++) {
// 如果存在重复字符,则获取最大的下标
i = Math.max(index[s.charCodeAt(j)], i);
// 每轮都拿之前与【当前字符一样】最大的下标跟当前下标的差做为最大的字串长度
len = Math.max(len, j - i + 1);
index[s.charCodeAt(j)] = j + 1;
}
return len;
}
至少有 K 个重复字符的最长子串
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var longestSubstring = function(s, k) {
let ans = 0
const n = s.length
for(let p = 1; p <= 26; p++){
const count = new Array(26).fill(0)
for(let i = 0, j = 0, tot = 0, sum = 0; i < n; i++){
const u = s[i].charCodeAt() - 97 ;
count[u]++
if(count[u] == 1) tot++
if(count[u] == k) sum++
while(tot > p){
const t = s[j++].charCodeAt() - 97;
count[t]--
if(count[t] == 0) tot--;
if(count[t] == k - 1) sum--;
}
if(tot === sum) ans = Math.max(ans, i - j + 1)
}
}
return ans
};
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var lengthOfLongestSubstringKDistinct = function(s, k) {
let l = 0, ans = 0;
const map = new Map();
const len = s.length;
for(let i = 0; i < len; i++) {
let c = s[i];
if(map.get(c)) {
map.set(c, map.get(c) + 1);
} else {
map.set(c, 1);
}
while (map.size > k) {
let ch = s[l];
map.set(ch, map.get(ch) - 1);
if (map.get(ch) === 0) {
map.delete(ch);
}
l++;
}
ans = Math.max(ans, i - l + 1);
}
return ans;
};