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

Example:

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

Algorithm:

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:

   If(maximum_l<current_l)

       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:

        If(maximum_l<current_l)

        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)
            current_l++;
 
            /*If the current character is present in the current substring*/
            else
            {
            /* 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:
O(d)
Go to top