Below is my method to find the longest substring having k
distinct characters.
I have used Set
to keep track of distinct characters.
public static int maxLengthSubstring(String str,int k) {
int i=0;
int j=i;
int max=0;
//use set to keep track of distinct characters
Set<Integer> set=new TreeSet<>();
char arr[] = str.toCharArray();
int len = arr.length;
while(i<len && j<len){
int c=arr[j];
set.add(c);
//if the number of distinct characters exceed the given limit
//then compute the length of substring containing them
if(set.size()>k){
int substrLen=Math.abs(i-j);
if(substrLen>max){
//update the length of maximum substring found
max=substrLen;
}
//move to the next character in the array
i=i+1;
j=i;
//clear the set containing previously found distinct characters
set.clear();
continue;
}
//if set contains the exact number for distinct characters
//then store the length of the substring and move to next iteration
if(set.size()==k){
int substrLen = Math.abs(i-(j+1));
if(substrLen>max){
//update the length of maximum substring found
max=substrLen;
}
}
j++;
}
return max;
}
The maximum length of input string can be up to million characters. The above method works fine for smaller strings but slows down if input string is large. How can I tweak my logic to improve running time for large strings?
A few test cases:
Input:
str="zxzxzxzxzx cvcvcvcvcvcvcvcvcv"
k=2
Output=18
Input:
str="aaaaaaaa abcabc aaaabbbbaaaabbbbbbabaa"
k=3
Output=23 (longest substring in this case is " aaaabbbbaaaabbbbbbabaa" including space character)