首页
学习
活动
专区
工具
TVP
发布

算法连载之求解不含有重复字符的最长子串长度

问题

给定一个字符串,找出其中不含有重复字符的最长子串长度。

示例 1:

输入: "abcabcbb"

输出: 3

解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"

输出: 1

解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"

输出: 3

解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。

暴力求解

枚举所有字符子串,获取长度最长的无重复字符子串。

分析程序,匹配在给定字符串中是否有重复字符isRepeating函数的时间复杂度是O(n)。因此,完成算法的时间复杂度是O(n³);空间复杂度是O(min(n, m)),其中n是字符串的长度,m是相异字符的数量。

从算法分析,如果从 0 到 j-1 是无重复字符子串,第j项元素同前面的任意一个元素重复,则不管第j项后面有无元素,0滑动窗口求解

1)如果从 0 到 j-1 是无重复字符子串,第j项元素同前面的任意一个元素重复,则不管第j项后面有无元素,0

2)移动开始索引位置,直到没有重复元素为止,此时为没有重复元素的子串,第j项作为结束索引继续向后移动,直到待判断的字符串结束为止,判断是否出现重复。如果出现重复,则继续重复2)。

滑动窗口算法优化了暴力求解法,当结束索引到第j项出现重复,不再向后继续判断,而是移动开始索引,直到没有重复元素为止,再继续向后移动结束索引,避免冗余判断。

在最坏情况下,字符串所有元素都会被开始索引和结束索引各遍历一次。时间复杂度是O(2n)=O(n)。空间复杂度是O(min(n, m)),其中n是字符串的长度,m是相异字符的数量。

分析算法发现,当出现一次重复时,我们移动开始索引位置,直到剔除重复元素为止。如果在移动过程中,未剔除重复元素,则一直要移动开始索引。因此,我们可以考虑让开始索引移动位置一步到位。

优化滑动窗口求解

优化滑动窗口求解方法,当出现判断字符为重复项时,直接将窗口的开始索引位置置于重复项的下一个元素继续判断。

时间复杂度是O(n)。空间复杂度是O(min(n, m)),其中n是字符串的长度,m是相异字符的数量。

性能分析

随机5000个字符的待匹配字符串进行测试:

The length of longest substring is 42 by Violence solve, using time is 2908 milliseconds.

The length of longest substring is 42 by Sliding Window solve, using time is 2 milliseconds.

The length of longest substring is 42 by Optimizing Sliding Window solve, using time is 2 milliseconds.

通过测试结果分析,移动窗口算法性能优异,时间复杂度是线性增长。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20190616A07PI300?refer=cp_1026
  • 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 cloudcommunity@tencent.com 删除。

扫码

添加站长 进交流群

领取专属 10元无门槛券

私享最新 技术干货

扫码加入开发者社群
领券