leetcode Question 45: Longest Substring Without Repeating Characters

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;
    }
};

8 comments:

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

    ReplyDelete
    Replies
    1. The duplicated char is not required to be on the i position.
      When 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.

      Delete
  2. This comment has been removed by the author.

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

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

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

    ReplyDelete
  6. int lengthOfLongestSubstring(string s) {
    int n = s.size();
    int res = 0;
    for (int i = 0; i < n; i++) {
    vector visited(256);

    for (int j = i; j < n; j++) {
    if (visited[s[j]] == true)
    break;
    else {
    res = max(res, j - i + 1);
    visited[s[j]] = true;
    }
    }
    visited[s[i]] = false;
    }
    return res;
    }

    ReplyDelete