最长无重复字符子串给定一个字符串 S (5<S 长度<50) ,请找出 S 中不含重复字符的最长子串的长度。 例如:s 为 ababc,最长不含重复字符的子串有 abc,所以不含重复字符的最长子串的长度为 3。
时间: 2025-02-28 22:25:33 浏览: 70
### 不含重复字符的最长子串长度
#### 滑动窗口算法解释
滑动窗口是一种常用的优化技术,用于解决涉及数组或字符串的问题。对于寻找不含重复字符的最长子串长度问题,可以利用两个指针来表示当前考察的子串范围,并通过哈希集合记录已访问过的字符。
当遇到已经存在于集合中的字符时,则移动左边界直到移除掉这个重复项为止;每次更新最大长度并继续向右扩展新加入的字符直至遍历结束[^1]。
```python
def length_of_longest_substring(s: str) -> int:
char_set = set()
l, res = 0, 0
for r in range(len(s)):
while s[r] in char_set:
char_set.remove(s[l])
l += 1
char_set.add(s[r])
res = max(res, r - l + 1)
return res
```
此方法的时间复杂度为O(n),其中n是字符串s的长度。因为每个索引最多只会被左右指针各访问一次。
#### 动态规划解法说明
另一种解决问题的方法是采用动态规划的方式。定义`dp[i]`代表以第i个位置结尾的最大不含有相同字母连续片段大小。如果当前位置上的字符从未出现过或者上一次出现在距离当前位置超过`dp[i-1]`的地方,则可以直接继承前一状态的结果加一;否则取两者之间的最小值作为新的状态转移方程[^2]。
然而需要注意的是,在实际编码过程中为了节省空间通常不会显式构建整个DP表而是仅保留必要的变量来进行迭代计算。
阅读全文
相关推荐

















