**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:**

**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:**