Description: Given a string, we have to find the length of the longest substring without repeating characters. 


The longest substring without repeating characters for “xabascus” is “bascu” with length 6.


The desired time complexity is O(n) where n is the length of the string.

Many different approaches may be used to solve the problem.

Method 1 (Simple)-O(n^3)

Here we consider all possible substrings and see if the substring has unique characters. There will be n*(n+1)/2 substrings. Checking whether a substring has unique characters or not can be done in linear time by scanning from left to right and keeping a map of visited characters.

Method 2 (Linear Time)

Lets consider a more efficient solution to solve the problem in linear time.

The steps to solve the problem are as follows:

1) Create an array ‘last’ containing 256 elements initialized to -1. An element of the array ‘last’ indicates the last index at which that element occurred in the string considered so far.

Eg: last[‘a’]=2 means that ‘a’ occurred last at the 2nd index.

2) Consider the string S whose substring we have to find. We assign last[S[0]]=0 for the 0th index.

Initialize maximum_l=1 and current_l to 1. Maximum_l indicates the maximum length of a possible substring found so far. On the other hand, current_l, tells the length of the current substring we are considering.

3) Scan the string S iteratively starting from the 2nd element using the index ‘i’ and consider the following cases:

-If the element S[i] doesn’t occur in the current sub-string, we increment current_l by 1.

-Else(element is present in the current substring), we update maximum_l using:


       maximum_l =current_l;

And we change current_l to exclude the previous occurrence of the current element.

    Current_l= i- last[S[i]];

4) After the iterations are complete, we again update maximum_l as follows:


        maximum_l =current_l;

Finally, the variable ‘maximum_l’ stores the length of the longest substring without any repeating characters.

Implementation in C:
/*The following function finds the length of the longest substring without repeating characters*/
int longsub(char *str)
            int n = strlen(str);
            int current_l = 1;  /*Length of current substring*/
            int maximum_l = 1;  /*Max length substring (required)*/
            int prev_index;  /* To store the previous index*/
            int i;
            int *last = (int *)malloc(sizeof(int)*NO_CHARS);
            /* Initialize 'last' array as -1 to indicae that character hasn't be visited yet.*/
            for (i = 0; i < NO_CHARS;  i++)
            last[i] = -1;
            last[str[0]] = 0;/*first character has been visited.*/
            /*Start scanning from the second character*/
            for (i = 1; i < n; i++)
            prev_index =  last[str[i]];
            /*If the current character isn't present in the current substring*/
            if (prev_index == -1 || i - current_l > prev_index)
            /*If the current character is present in the current substring*/
            /* We need to check whether length of current substring is greater than 'maximum_l'*/
            if (current_l > maximum_l)
                        maximum_l = current_l;
            current_l = i - prev_index;
            last[str[i]] = i; /* update the index of current character*/
            /* Iterations are complete, now check again to see current substring was the largest.*/
            if (current_l > maximum_l)
            maximum_l = current_l;
            free(last); /*free memory allocated for 'last'*/
            return maximum_l;
/*A function used to get minimum of 2 integers.*/
int min(int a, int b)
            return (a>b)?b:a;
Time Complexity:

O(n + d) where n is length of the input string and d is number of characters in input string alphabet.

Auxiliary Space:
Go to top