首页 > 代码库 > Leetcode: Longest Substring Without Repeating Characters
Leetcode: Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.
分析：该题目跟Minimum Substring Window 有相通之处，两个题目都是求一个特殊的window长度，Minimum Substring Window中求的是一个包含某string所有字符的最小window，而这道题是求一个所有字符都不同的最大window，两者都可以用two pointers的方法解。
此题两个关键点：(1) 如何扩展window (2)遇到重复字符时如何缩小window。
我们可以用一个数组保存已经出现的字符的index，如果字符未出现则为-1;当遇到重复字符时，我们只需将指向window开始的指针移动到第一个重复字符出现的位置之后即可。
时间复杂度为O(n)，空间复杂度O(1)。代码如下：
class Solution {public: int lengthOfLongestSubstring(string s) { int n = s.length(); if(n == 0) return 0; vector<int> pos(256, -1); int win_start = 0, max_width = 0; for(int win_end = 0; win_end < n; win_end++){ if(pos[s[win_end]] == -1){//not repeating character pos[s[win_end]] = win_end; max_width = max(max_width, win_end - win_start +1); }else{//repeating character for(; win_start < pos[s[win_end]]; win_start++){//eliminate characters from win_start to pos[s[win_end]] pos[s[win_start]] = -1; } win_start++; pos[s[win_end]] = win_end; } } return max_width; }};
Leetcode: Longest Substring Without Repeating Characters
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。