6)Longest K unique characters substring - (sliding window | variable size)

Given a string you need to print the size of the longest possible substring that has exactly K unique characters. If there is no possible substring then print -1.

Example 1:

Input:
S = "aabacbebebe", K = 3
Output: 7
Explanation: "cbebebe" is the longest 
substring with K distinct characters.

​Example 2:

Input: 
S = "aaaa", K = 2
Output: -1
Explanation: There's no substring with K
distinct characters.



c++ implementation:

 int longestKSubstr(string a, int k) 
    {
        int i=0;int j=0; int n=a.length();
     
        int len=-1;int count=0;
        map<char,int>map;
        while(j<n)
        {
            map[a[j]]++;
            if(map[a[j]]==1)
            count++;
        
            if(count==k)
            {
                len=max(len,j-i+1);
            }
            else if(count>k)
            {
                while(count>k)
                {
                    map[a[i]]--;
                    if(map[a[i]]==0)
                    count--;
                    
                    i++;
                }
                len=max(len,j-i+1);
            }
            j++;
        }
        return len;
    }
Time Complexity: O(n) 
space Complexity: O(n) 



darkmode