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 –
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 |
#include <iostream> #include <string> using namespace std; // define character range #define CHAR_RANGE 128 // Function to find longest substring of given string containing // k distinct characters using sliding window string longestSubstr(string str, int k, int n) { // stores longest substring boundaries int end = 0, begin = 0; // set to store distinct characters in a window unordered_set<char> window; // count array to store frequency of characters present in // current window // we can also use a map instead of count array int freq[CHAR_RANGE] = { 0 }; // [low..high] maintain sliding window boundaries for (int low = 0, high = 0; high < n; high++) { window.insert(str[high]); freq[str[high]]++; // if window size is more than k, remove characters from the left while (window.size() > k) { // if the frequency of leftmost character becomes 0 after // removing it in the window, remove it from set as well if (--freq[str[low]] == 0) window.erase(str[low]); low++; // reduce window size } // update maximum window size if necessary if (end - begin < high - low) { end = high; begin = low; } } // return longest substring found at str[begin..end] return str.substr(begin, end - begin + 1); } // main function int main() { string str = "abcbdbdbbdcdabd"; int k = 2; int n = str.length(); cout << longestSubstr(str, k, n); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
import java.util.HashSet; import java.util.Set; class LongestSubstr { // define character range public static final int CHAR_RANGE = 128; // Function to find longest substring of given string containing // k distinct characters using sliding window public static String longestSubstr(String str, int k) { // stores longest substring boundaries int end = 0, begin = 0; // set to store distinct characters in a window Set<Character> window = new HashSet<>(); // count array to store frequency of characters present in // current window // we can also use a map instead of count array int[] freq = new int[CHAR_RANGE]; // [low..high] maintain sliding window boundaries for (int low = 0, high = 0; high < str.length(); high++) { window.add(str.charAt(high)); freq[str.charAt(high)]++; // if window size is more than k, remove characters from the left while (window.size() > k) { // if the frequency of leftmost character becomes 0 after // removing it in the window, remove it from set as well if (--freq[str.charAt(low)] == 0) { window.remove(str.charAt(low)); } low++; // reduce window size } // update maximum window size if necessary if (end - begin < high - low) { end = high; begin = low; } } // return longest substring found at str[begin..end] return str.substring(begin, end + 1); } // main function public static void main(String[] args) { String str = "abcbdbdbbdcdabd"; int k = 2; System.out.print(longestSubstr(str, k)); } } |
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 our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
Leave a Reply
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));