给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
时间: 2023-04-16 09:04:42 浏览: 81
题目描述:
给定一个字符串 s,请你找出其中不含有重复字符的最长子串的长度。
示例:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
相关问题
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。的c++代码
以下是使用滑动窗口算法实现的 C++ 代码:
```c++
#include <unordered_set>
int lengthOfLongestSubstring(string s) {
int n = s.size();
unordered_set<char> set;
int ans = 0, i = 0, j = 0;
while (i < n && j < n) {
if (set.find(s[j]) == set.end()) {
set.insert(s[j++]);
ans = max(ans, j - i);
} else {
set.erase(s[i++]);
}
}
return ans;
}
```
该算法使用双指针维护一个滑动窗口,滑动窗口中存储的是当前不含重复字符的子串。使用 `unordered_set` 来判断是否出现重复字符,如果出现重复字符,则将左指针向右移动一位,并从集合中删除对应的字符。如果没有出现重复字符,则将右指针向右移动一位,并将新的字符加入集合中。最后返回最长子串的长度。
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度
这是一个经典问题,可以使用滑动窗口算法来解决。
具体思路如下:
1. 定义一个窗口,用来存储不重复的字符。
2. 定义两个指针 left 和 right,分别指向窗口的左右边界。
3. 循环遍历字符串 s,每次将 right 指针向右移动一位,并将对应的字符加入窗口中。
4. 如果加入字符后窗口中出现了重复字符,则将 left 指针向右移动,直到窗口中不再出现重复字符。
5. 每次移动指针时,记录窗口的大小,并更新最大窗口大小。
6. 循环遍历完字符串 s 后,最大窗口大小即为所求的最长子串长度。
以下是示例代码实现:
```python
def lengthOfLongestSubstring(s: str) -> int:
left, right = 0, 0
max_len = 0
window = set()
while right < len(s):
if s[right] not in window:
window.add(s[right])
right += 1
max_len = max(max_len, len(window))
else:
window.remove(s[left])
left += 1
return max_len
```
时间复杂度为 O(n),空间复杂度为 O(k),其中 k 为字符集大小。