O(kn), if k is constant
=O(n)
Algorithm working->
1. Move in the string from 0th index,. every time next character is encountered then increment index of A[] and add that character and increment the values of B[] (that is counting no. of repeated characters to same index value and distinct character to next index).
2.To find the max span for k unique character. After finding k distinct characters from starting, all values of B array are added to find length of the span and that value is compared with the maximum value returned by remaining array ( i.e. value returned by max_span(i+1,k,j)). Elements which we are considering in the same span have same span_no[] value so that we can add B[] array values for those indexes to find length of the span.
3. Give span_no[] array same value for the indexes which are in same span. now when we move to next span, add B[] values for the indexes which have same span_no[] values and move to next span. But here, add the last element of previous span in the next span ex - "aaaabbaccccc" for 2 unique characters, this string will break to 2 spans "aaaabba" and "accccc" so for next span we will assign span_no[] another (unique) value for all elements in that span.
Taking help of 3 arrays
A[] -> to store all unique characters in an array, array size is in worst case = number of characters in string ( i.e. if all consecutive elements are different if "abcdef" then array size will be 6) if "aaaabba" then 'a' before 'b' is different from 'a' after b so array will store A[0]='a', A[1]='b', A[2]= 'a',
B[] -> number of times a distinct character present in the string , for "aaaabba" this will store -> B[0] =4 ,B[1] = 2,B[2] = 1
span_no[] -> first span possible is "aaaabba",span_no[] will help to tell the elements which are present in current span, so span_no will store -> span_no[0]=0, span_no[1]=0, span_no[2] =0.
int len; // number of unique characters
char A[n];
int B[n]; //<- initialize them to 0
int span_no[n], j=0;
int max_span(int i,int k, int j) // i = current index in string, k = remaining distinct characters in this span, j= index position for contracted array
{
if(i==0)
{
A[j]=string[i];
B[j]++;
return max_span(i+1,k-1,j);
}
else if (i==n)
return 0;
else if(string[i] == string[i-1])
{
A[j]=string[i]; B[j]=+1;
return max_span(i+1,k,j);
}
else //then search for the term which is equal to this character in current span in O(k)
{
++j, B[j]+=1; A[j]=string[i];
int temp_i =j-1,found=0; ++j;
while((temp_i!=0)&&(span_no[ j ]==span_no[temp_i])) // if that span contains same character earlier also then count this, element in the same span otherwise it will be taken as distinct element in that case if distinct character length is full (i.e. k==0), then add this element in next span
{
if(A[ j ]==A[temp_i])
found=1; --temp_i;
}
if(found==1 && k!=0) // if found then add to that span only
{
span_no[j]=span_no[j-1];
max_span(i+1,k,j);
}
else if(!found && k==0) //if not found and k is reached 0 then add to next span
{
temp_j=j-1; add=0;
while(span_no[--temp_j]==span_no[j-1]) //count all characters in this span and move to next span
{
add+=B[temp_j];
}
span_no[j-1]+=1; //include last element also in the next span
span_no[j]=span_no[j-1];
int u=max_span(i+1,len,j);
return max(add , u);
}
else //if not found and distinct character count is remaining in that span then add to the current span only
{
span_no[j]=span_no[j-1];
max_span(i+1,k-1,j);
}
}
}