滑窗算法python实现返回最长字符子串
时间: 2023-07-31 21:09:04 浏览: 53
下面是使用滑动窗口算法实现返回最长字符子串的Python代码:
```
def longest_substring(s):
n = len(s)
i = j = 0
max_len = 0
sub_str = ''
set_s = set()
while i < n and j < n:
if s[j] not in set_s:
set_s.add(s[j])
j += 1
if j - i > max_len:
max_len = j - i
sub_str = s[i:j]
else:
set_s.remove(s[i])
i += 1
return sub_str
```
该函数接受一个字符串作为输入,返回这个字符串中最长的不重复的连续子串。
具体实现过程为,在一个窗口内使用两个指针i和j,i指向窗口的左端,j指向窗口的右端。同时维护一个集合set_s,用于存储窗口内的字符。如果当前字符不在set_s中,将其加入set_s,同时将窗口右移一位,并更新最长子串的长度和内容;如果当前字符已经在set_s中,将窗口左移一位,并将set_s中对应的字符删除。
该算法的时间复杂度为O(n),其中n为字符串的长度,空间复杂度为O(min(m,n)),其中m为字符集的大小。
相关问题
python求两个字符串的最长公共子串
你好,关于你的问题,我可以回答。求两个字符串的最长公共子串可以使用动态规划算法。具体步骤是:先构造一个二维数组,行数为第一个字符串的长度,列数为第二个字符串的长度。然后,遍历数组,如果两个字符串的某个字符相同,就将该位置的值设为左上角位置的值加一,否则设为零。最后,找到数组中的最大值,该值所在的位置就是最长公共子串的末尾位置,根据该位置和最大值可以求出最长公共子串。希望能帮到你。
python最长连续子串
可以使用动态规划算法来解决这个问题。具体步骤如下:
1. 定义一个列表 dp,其中 dp[i] 表示以第 i 个字符为结尾的最长连续子串的长度。
2. 初始化 dp 列表,将 dp 的每个元素都设置为 1。
3. 遍历字符串,对于每个字符 i,判断它和前一个字符 i-1 是否相等。如果相等,说明可以将当前字符加入到前一个字符的最长连续子串中,此时 dp[i] = dp[i-1] + 1;否则,当前字符单独构成一个新的连续子串,此时 dp[i] = 1。
4. 在遍历过程中,记录最大的 dp[i] 值,即为最长连续子串的长度。
下面是 Python 代码实现:
```python
def max_continuous_substring(s):
n = len(s)
dp = [1] * n
max_len = 1
for i in range(1, n):
if s[i] == s[i-1]:
dp[i] = dp[i-1] + 1
max_len = max(max_len, dp[i])
return max_len
```
你可以调用这个函数,传入一个字符串参数,它会返回该字符串的最长连续子串长度。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)