#  Longest Substring Without Repeating Characters

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

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

"pwwkew" wke or kew two continue char and then again
"ckilbkd" ckilb or ilbkd repeated char but it can count both from front or back
"tmmzuxt" mzuxt two continue char means discard before all char
"wobgrovw" bgrovw repeated char but it can count both from front or back
"abcdabcd" abcd repeat substring
``````int lengthOfLongestSubstring(char* s) {

int size = strlen(s);
int ans = 0;
int temp = 0;
int same = -1;
int again = 0;
unsigned int arr = {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;
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;
}
``````