Longest substring of given string containing distinct characters

Given a string, find the longest substring of given string containing distinct characters.

 

For example,

string = ‘findlongestsubstring’
The longest substring with all distinct characters is ‘dlongest’ or ‘ubstring’
 

string = ‘longestsubstr’
The longest substring with all distinct characters is ‘longest’
 

string = ‘abbcdafeegh’
The longest substring with all distinct characters is ‘bcdafe’
 

string = ‘aaaaaa’
The longest substring with all distinct characters is ‘a’

 


 

A simple solution would be to generate all substrings of the given string and return longest substring containing all distinct characters. The time complexity of this solution would be exponential.
 

We can easily solve this problem in O(n) time. The idea is to use sliding window technique. In sliding window technique, we maintain a window that satisfies the problem constraints. The window is unstable if it violates the problem constraints and it tries stabilize by increasing or decreasing it’s size.

So for current problem, the window (subarray) is stable if it contains all distinct characters at any point. If window contains duplicates characters, it shrinks by removing characters from the left till it becomes stable again. The window in the stable state tends to increase its size by adding characters to it till it becomes unstable again. The process continues till the window reaches the last character in the string. At each point the window size changes, we update the maximum window size.

 
C++ implementation –
 

Download   Run Code

Output:

bcdafe

 
The time complexity of above solution is O(n) as it does 2 traversal of the given string.

 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂