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.

Below is C++ and Java implementation of the idea –

Java

Output:

bdbdbbd

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

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Subscribe
Notify of
Guest
Tarun Mitra

Single traversal Solution:

String str =”abcbdbdbbdcdabd”;
int k = 2;
HashMap map = new HashMap();
int start = 0;
int maxi = -1;
int length = 0;
for(int i=0;i<str.length();i++){
if(!map.containsKey(str.charAt(i)))
map.put(str.charAt(i),0);
map.put(str.charAt(i),map.get(str.charAt(i))+1);
if(map.size() <= k && length k){
while(map.size() > k){
map.put(str.charAt(start),map.get(str.charAt(start))-1);
if(map.get(str.charAt(start)) == 0)
map.remove(str.charAt(start));
start++;
}
}
}

if(maxi != -1)
System.out.println(str.substring(maxi,maxi+length));

Guest
Naveen Kumar Krishnasamy

// string str = “aaaa”;
// int k = 1;
For this the output should be ‘a’ , but output is ‘aaaa’

Guest

while(window.size() > k) can be replaced by ‘if’