[3] Longest Substring Without Repeating Characters

© Jarvus Chen / www.jarvus.net

Description

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.

Required knowledge

All ASCII are 128 words.

ASCII from https://en.wikipedia.org/wiki/ASCII

How to get char* length in C?

char* str = "12345";
int size = strlen(str);

size is 5 for the return value.

My solution

I used arr as 128 ASCII char marks to identify has the next char been before. If it is the first time be, I will store its next position in arr. Then, if next char has been before, use arr value as the next position ( kind of loop ).

You can't use more than O(n^2) solution because of "Time Limit Exceeded" in a very long long input string.

To fullfill all condition, there are some issue you have to notice.

int lengthOfLongestSubstring(char* s) {

    int size = strlen(s);
    int ans = 0;
    int temp = 0;
    int same = -1;
    int again = 0;
    unsigned int arr[128] = {0};
    unsigned int start = 0;
    unsigned int doing = 0;
    int idx;

    while( doing < size ){

        idx = s[doing];
        // been this char
        if ( arr[idx] != 0 && again == 0){
            doing = arr[idx];
            for( int i = 0 ; i < 128 ; i++ ){
                arr[i] = 0;
            }

            temp = 0;
            again = 1;

        }
        // first be
        if ( arr[idx] == 0 && again == 0){
            arr[idx] = doing + 1;
            doing++;
            temp++;
            if ( temp > ans){
                ans = temp;
            }
        }
        same = idx;
        again = 0;

    }
    return ans;
}

Others solution

https://discuss.leetcode.com/topic/53272/4ms-c-solution-beats-95-code-use-array-int-h-128/7

It h is the same with my arr which is marks for all ASCII char. Its code has a one more smart part. It return to previous position only when the range is larger than current max range.

int lengthOfLongestSubstring(char* s) {
  int h[128];
  int beginCurr = 0;
  int max=0,i=0;
  for(i=0;i<128;i++){
    h[i]=-1;
  }
  i=0;
  while(*s){
    //check whether current character has been seen since beginCurr
    if(h[*s]>=beginCurr){
      if(i-beginCurr>max)
        max=i-beginCurr;
        beginCurr=h[*s]+1;
    }
    h[*s]=i;
    i++;
    s++;
  }
   if(i-beginCurr > max)
   {
        max = i - beginCurr;
   }
  return max;
}