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