[3] Longest Substring Without Repeating Characters

© Jarvus Chen / www.jarvus.net


Given a string, find the length of the longest substring without repeating characters.


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.

input string answer issue
"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[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;
            if ( temp > ans){
                ans = temp;
        same = idx;
        again = 0;

    return ans;

Others solution


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;
    //check whether current character has been seen since beginCurr
   if(i-beginCurr > max)
        max = i - beginCurr;
  return max;

results matching ""

    No results matching ""