首页 > 代码库 > 3. Longest Substring Without Repeating Characters
3. Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
分析
假设子串里含有重复字符，则父串一定含有重复字符，单个子问题就可以决定父问题，因此可以用贪心法Greedy Algorithm。跟动规不同，动规里，单个子问题只能影响父问题，不足以决定父问题。从左往右扫描，当遇到重复字母时，以上一个重复字母的 index+1，作为新的搜索起始位置，直到最后一个字母，复杂度是 O(n)。
该题的关键在于利用一个数组记录每个字母上一次的出现位置 postion
time complexity O(n)
space complexity O(1)
class Solution {public:int lengthOfLongestSubstring(string s) {int start = 0, maxlen = 0, position[128] = {-1};fill(position, position + 128, -1);for( int i = 0; i < s.size(); ++i){if( position[s[i]] >= start){//说明在start后面出现了两个重复字母，需要计算子串maxlen = max( maxlen, i - start);start = position[s[i]] + 1;}position[s[i]] = i;}return max(maxlen, (int)s.size() - start);//不要忘记最后字符串结尾的计算}};
来自为知笔记(Wiz)
3. Longest Substring Without Repeating Characters
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。