求字符串的最长不重复子串JS
时间: 2024-09-13 17:08:01 浏览: 13
在JavaScript中,求一个字符串的最长无重复字符子串通常可以使用滑动窗口或哈希集合的方式来解决。这里是一个基于哈希集合的解决方案:
```javascript
function lengthOfLongestSubstring(s) {
let maxLength = 0;
let seen = {};
let left = 0;
for (let right = 0; right < s.length; right++) {
if (seen[s[right]]) {
left = Math.max(left, seen[s[right]] + 1);
}
maxLength = Math.max(maxLength, right - left + 1);
seen[s[right]] = right;
}
return maxLength;
}
```
这个函数的工作原理是维护一个左边界`left`和右边界`right`,并在每个位置检查从`left`到当前位置是否有重复字符。如果有,移动左边界`left`到重复字符的下一个位置。同时更新最长子串的长度`maxLength`。
相关问题
用js从一个字符串中提取不重复最长子串。限定ES5语法
使用JavaScript ES5语法从字符串中提取不重复的最长子串可以通过以下步骤实现:
1. 使用两个指针,一个开始(start)和一个结束(end),来表示当前遍历的子串的范围。
2. 移动结束指针来逐步扩大子串的范围,同时用一个对象或者数组来记录当前子串中字符的出现情况。
3. 如果遇到已经出现过的字符,就移动开始指针,直到该字符不再出现在子串中,以此来保证子串中不会有重复的字符。
4. 在移动指针的过程中,记录并更新最长不重复子串的长度和内容。
下面是使用ES5语法实现的示例代码:
```javascript
function longestUniqueSubstring(str) {
var start = 0, maxLen = 0, maxStr = '';
var charIndexMap = {}; // 用于记录字符最后出现的位置
for (var end = 0; end < str.length; end++) {
var char = str[end];
// 检查字符是否在当前子串中
if (charIndexMap.hasOwnProperty(char)) {
// 如果字符出现过,移动开始指针到该字符上次出现位置的下一个位置
start = Math.max(charIndexMap[char] + 1, start);
}
// 更新字符的最后出现位置
charIndexMap[char] = end;
// 更新最长不重复子串
if (end - start + 1 > maxLen) {
maxLen = end - start + 1;
maxStr = str.substring(start, end + 1);
}
}
return maxStr;
}
// 示例
var result = longestUniqueSubstring("abcabcbb");
console.log(result); // 输出最长不重复子串
```
在这段代码中,`longestUniqueSubstring`函数接收一个字符串`str`作为参数,通过遍历字符串并使用一个对象`charIndexMap`记录字符位置,找到并返回最长的不重复子串。
给定字符串找出不含重复字符串的子串长度,JS
在JavaScript中,找到一个字符串中所有不包含重复字符的最长子串的长度,可以使用滑动窗口算法。这里有一个简单的步骤描述:
1. 初始化两个指针,`left` 和 `right`,分别指向字符串的起始位置。
2. 创建一个哈希集合(或称为Set)`seen`,用于存储当前子串中的字符。
3. 当`right`向右移动时,检查`right`位置的字符是否已经在`seen`中。如果不在,将该字符添加到`seen`中,同时更新`maxLength`(即最长子串长度)和`result`(最长子串)。
4. 如果在,移除`left`位置的字符(从`seen`中删除)并将`left`向右移动一位,直到`left`位置的字符不再存在于`seen`中。
5. 循环结束后,`maxLength`就是我们需要的答案。
下面是一个具体的实现示例:
```javascript
function lengthOfLongestSubstring(s) {
let left = 0;
let maxLength = 0;
let seen = new Set();
for (let right = 0; right < s.length; right++) {
if (!seen.has(s[right])) {
seen.add(s[right]);
maxLength = Math.max(maxLength, right - left + 1);
} else {
seen.delete(s[left]);
left++;
}
}
return maxLength;
}
```
你可以用这个`lengthOfLongestSubstring`函数来处理任何给定的字符串,例如`lengthOfLongestSubstring("abcabcbb")`将返回`3`,因为最长的无重复字符子串是`"abc"`。