**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.**

Analysis:

Set two pointers, i,j, scan the string from the start to the end. Set a table to store if the character has occurred.

If s[j] has occurred in S[i..j-1], compute current length and compare to the max length. Then table[s[i]]=false; i++; If s[j] has not occurred in S[i..j-1], table[s[j]]=true; j++;

Source code:

class Solution { public: int lengthOfLongestSubstring(string s) { // Start typing your C/C++ solution below // DO NOT write int main() function if(s.size()==0){return 0;} if(s.size()==1){return 1;} int i=0; int j=0; int maxl = 0; map<char,bool> table; while ( (i<s.size()) && (j<s.size()) ){ if (table[s[j]]==false){ table[s[j]]=true; maxl = max(maxl,j-i+1); j++; }else if (table[s[j]]==true){ maxl = max(maxl,j-i); table[s[i]]=false; i++; } } return maxl; } };

被重复的不一定在位置i上

ReplyDeleteThe duplicated char is not required to be on the i position.

DeleteWhen the current char is duplicated, only i++ is conducted, j is not moving.

if str = "abcc..." when str[j] is 2nd 'c', "i++" will repeat three times, until goes to 2nd c, at the same time the max length is still len("abc")=3.

try this case?

ReplyDeleteabcdceadf

This comment has been removed by the author.

ReplyDeleteThis code seems to be wrong for test cases that the longest substring appear at the end, like "abcdceadf" by Yang YUAN or "bcdcxyz".

ReplyDeleteHere is my code, passed leetcode online judge. https://juliachenonsoftware.wordpress.com/2015/04/02/longest-substring-without-repeating-characters/

ReplyDeleteGreat article. This is a very popular interview question. I also wrote an in-depth analysis at https://goo.gl/UaLw1E.

ReplyDelete