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 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:
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:
Finally, the variable ‘maximum_l’ stores the length of the longest substring without any repeating characters.
O(n + d) where n is length of the input string and d is number of characters in input string alphabet.