leetcode——中级算法——数组和字符串——无重复字符的最长字串
给定一个字符串,找出不含有重复字符的最长子串的长度。
示例1
输入: "abcabcbb"
输出: 3
解释: 无重复字符的最长子串是 "abc",其长度为 3
示例2
输入: "bbbbb"
输出: 1
解释: 无重复字符的最长子串是 "b",其长度为 1。
示例3
输入: "pwwkew"
输出: 3
解释: 无重复字符的最长子串是 "wke",其长度为 3。
请注意,答案必须是一个子串,"pwke" 是一个子序列 而不是子串。
思路
设置保存当前不含重复元素的子串 sub=" ",设置字串的最大长度 maxLen = 0.
循环遍历每个字符c,若:
- 字串sub中不包含c,则将c加入sub,更新最大长度maxLen
- sub包含c,则需要删除sub中c及c之前的元素,然后将c加入sub。
最后返回maxLen即可。
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s) {
let maxLen = 0;
let sub = '';
for (let c of s) {
if (sub.includes(c)) { // 子串中含有当前字符
sub = sub.slice(sub.indexOf(c) + 1) + c; // 将子串更新
} else { // 不含
sub += c;
maxLen = Math.max(maxLen, sub.length); // 更新最大长度
}
}
return maxLen;
};