最长不重复子串问题:给定一个字符串S,返回S中所有字符的最长不重复子串的长度。如果S为空,返回0。
时间: 2023-05-24 07:06:36 浏览: 63
算法思路:
使用双指针left和right维护一个滑动窗口,表示当前不重复子串的范围。初始时,left和right都指向字符串的第一个字符。
在移动right指针的过程中,维护一个哈希表或数组,记录每个字符最后一次出现的位置。假设当前right指针指向的字符是s,如果s已经在哈希表中存在(即s在[left,right)范围内),则将[left,right)区间中所有s之前的字符都从哈希表中删除,同时将left指针移到s上一次出现位置的下一个位置,即left=hash[s]+1。
同时,每次移动right指针时,都需要更新该字符最后一次出现的位置hash[s]=right。
在移动right指针的过程中,使用一个变量maxlen记录最长不重复子串的长度。
算法实现:
时间复杂度为O(n),空间复杂度为O(n)。
Python代码实现:
相关问题
Python代码实现:最长不重复子串问题:给定一个字符串S,返回S中所有字符的最长不重复子串的长度。如果S为空,返回0。
示例:
输入: "abcabcbb"
输出: 3
解释: 最长的不重复子串是 "abc",其长度为3。
输入: "bbbb"
输出: 1
解释: 最长的不重复子串是 "b",其长度为1。
输入: ""
输出: 0
代码实现:
```python
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
left = res = 0
lookup = set()
for right in range(len(s)):
while s[right] in lookup:
lookup.remove(s[left])
left += 1
lookup.add(s[right])
res = max(res, right - left + 1)
return res
```
解析:
使用一个滑动窗口来维护最长的不重复子串。初始时,窗口左右端点都指向字符串的起始位置。然后逐个向右移动右端点,并将右端点指向的字符加入到集合中。
如果当前字符已经在集合中存在,说明窗口中已经存在重复字符,那么就需要从窗口左端点开始移动,并将左端点指向的字符从集合中删除,直到窗口中不再有重复的字符。
在移动窗口的过程中,我们需要不断地记录最长的不重复子串的长度,并更新结果res。
时间复杂度:O(n)
空间复杂度:O(n)
python最长不重复子串问题:给定一个字符串S,返回S中所有字符的最长不重复子串的长度。如果S为空,返回0。 例如: 输入:S = “abcabcbb” 输出:3 解释:最长不重复子串是"abc",长度为3。 输入:S = “bbbbb” 输出:1 解释:最长不重复子串是"b",长度为1。
可以使用滑动窗口算法来解决这个问题。具体来说,我们可以使用两个指针left和right来表示当前考虑的子串的左右边界,使用一个哈希表来记录每个字符最后一次出现的位置。初始时,left和right都指向字符串的开头,哈希表为空。然后,我们不断地将right向右移动,直到遇到一个重复的字符。此时,我们可以更新最长不重复子串的长度,并将left指向重复字符的下一个位置。同时,我们需要将哈希表中所有在left之前的字符的位置信息删除,以确保我们只考虑当前子串中的字符。最后,我们将right继续向右移动,重复上述过程,直到right到达字符串的末尾。
以下是Python代码实现:
def lengthOfLongestSubstring(s: str) -> int:
n = len(s)
if n == 0:
return 0
left, right = 0, 0
max_len = 0
char_dict = {}
while right < n:
if s[right] in char_dict and char_dict[s[right]] >= left:
left = char_dict[s[right]] + 1
char_dict[s[right]] = right
max_len = max(max_len, right - left + 1)
right += 1
return max_len
输入:S = “abcabcbb”
输出:3
解释:最长不重复子串是"abc",长度为3。
输入:S = “bbbbb”
输出:1
解释:最长不重复子串是"b",长度为1。