Find the longest substring of given string containing k distinct characters

Given a string and a positive number k, find the longest substring of given string containing k distinct characters. If k is more than number of distinct characters in the string, return the whole string.

 


For example, consider string abcbdbdbbdcdabd


For k = 2, o/p is ‘bdbdbbd’
For k = 3, o/p is ‘bcbdbdbbdcd’
For k = 5, o/p is ‘abcbdbdbbdcdabd’


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

We can easily solve this problem in O(n) time and O(n) space. 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 k distinct characters at any point. If window contains less than k distinct characters, it expands by adding characters to it from the right else if window contains more than k distinct 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. We continue this process 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:

bdbdbbd

 
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 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz