LeetCode No3. 无重复字符的最长子串 题解
一、题目
给定一个字符串 s ,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,“pwke” 是一个子序列,不是子串。
示例 4:
输入: s = “”
输出: 0
提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
二、算法思想
这道题可以使用暴力解法提取每一个子串,但是考虑到效率太低,因此我们思考能不能减少子串的无效提取次数。
我们可以采用动态规划的思想,先选取字符串的前一部分,逐步递推得到最终解。
例如以 “abcbad” 为例,记 max 表示最长无重复子串长度
1、从 “a” 开始,这时 max = 1
2、对 “ab” 而言,看成是 “a” + “b”,这里因为 “b” 不与 “a” 重复,因此 “ab ”的 max 就是 “a” 的 max + 1
3、对 “abc” 而言,看成是 “ab” + “c”,同上,max = max + 1 = 3
4、对 “abcb” 而言,看成是 “abc” + “b”,这时因为 “b” 在 “abc” 中,因此 max 不变。
5、对 “abcba” 而言,看成是 “abcb” + “a”,同样,“a” 在 “abcb” 中,因此 max 不变
6、对“abcbad” 而言,看成是 “abcba” + “d”,这时 “d” 不在 “abcba” 中,按理说 max = max+ 1。但是这里 “d” 并没有和前面的 “abc” 连接一起,而是和 “cba” 连成了 “cbad”。
于是我们发现,只要出现了重复的单个字符,从最左边的子串就已经连接不上了,后面只可能是最右边出现连续子串。
所以在原来的子串右边接上一个字符后:
- max 可能是原来子串的 max(字符重复),即像步骤 4/5 中一样;
- max 可能是从右边新接上的字符向左数得到的最大不重复长度,因为从最右边向左数,最长的长度比 max 大,即像步骤 2/3/6 一样
也就是说,这实际上就是一个 max 值的更新问题,就是比较原来的 max 和添加新字符后从右到左不重复的最大长度问题。因此我们可以总结出我们的核心算法,并对该算法进行了一些优化:
- 从最左边的第一个字符开始,记为子串 s,令 max = 1;
- 选取临近的右边第一个字符 c,进行判断并更新 max:
- 如果 s 中含有 c,则将 s 中字符 c 左边的部分删去(包括字符 c),这样得到的 s 中将不含重复的字符。
- 如果 s 中不含有 c,啥也不做。
- 在 s 的最右边添加字符 c;
- 比较 s 的长度和 max 的大小,较大者赋予 max;
- 重复 2、3、4 步骤,直到没有新字符可以添加为止。
这里我们保证了 s 是不重复的子串,并且 s 的左边一个字符就刚好是 s 末尾的字符,因此 s 的长度就是从右到左不重复的最大长度,这样就避免了傻傻的搜索。
但是判断 s 中是否含有 c 仍需要遍历搜索,因为我们的 s 始终是不重复并且可能是乱序的,没有较好的优化方法。
三、示例
记原始的子串 max 为 former_max,右到左不重复的最大长度(即 s 的长度)为 s_len。
对于串 “abacdaeb”,按照上述算法进行如下步骤:
四、代码
class Solution {
public:
// s:字符串
// start:寻找位置
// end:终止位置
// c:寻找的字符
// index:该字符在 s 中的位置
bool find(const string &s, int start, int end, char c, int &index) {
for (int i = start; i < end; ++i)
if (c == s[i]) {
index = i;
return true;
}
return false;
}
int lengthOfLongestSubstring(string s) {
if (s.size() == 0) return 0; // 如果为空串,直接返回 0
int max = 1, p = 0, index = 0; // max 储存最大值,p 表示可能的最大子串的起始位置,index 存储重复字符的位置
for (int i = 1; i < s.size(); ++i) // 遍历字符
{
if (find(s, p, i, s[i], index)) p = index + 1; // 如果找到重复的字符,更新位置 p
max = max > i - p + 1? max : i - p + 1; // 更新 max
}
return max; // 返回结果
}
};
五、复杂度分析
(1)时间复杂度:
上述代码遍历的复杂度是 O(n),每一层遍历最多耗时 O(n),因此最坏情况下是 O(n2)。
但是往往不会达到 O(n2),大多数情况下(字符分布重复均匀)是 O(n),即 find 函数找常数个字符就找到了目标。
(2)空间复杂度
没有创建额外的大量存储开销,空间复杂度为 O(1)。
六、算法评价
LeetCode 中:
执行用时:0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗:6.7 MB, 在所有 C++ 提交中击败了96.80%的用户
提交了很多次,整体时间稳定在 0 ~ 4ms,内存消耗稳定在 6.6 ~ 6.7ms。
相关文章
- LeetCode 387. 字符串中的第一个唯一字符
- 【LeetCode】前 K 个高频元素 [M](堆)
- 【LeetCode】无重复字符的最长子串 [M](动态规划)
- LeetCode_BFS_DFS_简单_1971.寻找图中是否存在路径
- LeetCode_BFS_中等_934.最短的桥
- LeetCode_前缀和_哈希表_中等_523.连续的子数组和
- LeetCode_字符串_简单_387. 字符串中的第一个唯一字符
- LeetCode_排序_中等_406.根据身高重建队列
- LeetCode_双指针_中等_80.删除有序数组中的重复项II
- LeetCode·每日一题·2287.重排字符形成目标字符串·数学
- LeetCode·455.分发饼干·贪心
- LeetCode·491.递增子序列·递归+回溯+剪枝
- leetcode || Spiral Matrix
- leetcode第一刷_Rotate Image
- leetcode 春季编程大赛-个人赛
- [LeetCode] 750. Number Of Corner Rectangles 边角矩形的数量
- leetcode 4 寻找两个正序数组的中位数
- leetcode 714 买卖股票的最佳时机含手续费
- leetcode 19 删除链表的倒数第n个节点