Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Longest Sub-string with at most K Distinct Characters

Moderate
0/80
Average time to solve is 35m
30 upvotes
Asked in companies
AmazonSAP LabsHike

Problem statement

You are given string S of length N, and an integer K. Your task is to find the length of the longest substring that contains at most K distinct characters.

Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line contains an Integer 'T' which denotes the number of test cases/queries to be run. 
Then the test cases follow. 

The first line of input for each test case/query contains an integer K.

The second line of input for each test case/query contains a string S.
Output Format:
For each test case, print the length of the longest substring that contains at most K distinct characters.

Output for every test case will be printed in a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 10
1 <= K <= 26
1 <= N <= 10^4

Time Limit: 1sec
Sample Input 1:
2
2
abcba
1
abccc
Sample Output 1:
3
3
Explanation of the Sample Input1:
Test Case 1:
K = 2 in the first test case so we can choose substring ‘bcb’ having 2 distinct characters which are less than equal to K=2. 
We cannot get any other substring of length 4 or greater having distinct characters less than equal to 2.
Test Case 2:
K = 1 in the second test case so we can choose substring ‘ccc’ having only 1 distinct character which is less than equal to K=1. 
We cannot get any other substring of length 4 or greater having distinct characters less than equal to 1.
Hint

Try to check every substring.

Approaches (4)
Brute Force
  • We will generate all the substrings using 2 nested for loops and we will have a ‘CHECK’ function which returns true if the number of distinct character in the substring is less than equal to K otherwise false.
  • We will have an ans variable initialize to 0. We will call the ‘CHECK’ function with every substring and if it returns true then
    • ANS = MAX(ANS , CURRENT_SUBSTRING.SIZE())
  • To implement the check function we will have K and substring S as inputs and we will create an array of size 26 let’s call this ‘FREQ’ and initialize all position with 0.
    • Increase the frequency of every character in the substring S.
      • FREQ[S[i]-’a’]++
    • Have a variable ‘DISTINCT’ = 0
      • Then run a loop from i = 0 to i = 25 and increase the ‘DISTINCT’ if FREQ[i] is non-zero.
    • Return true if DISTINCT <= K otherwise return false
  • Finally, return ANS which have our required answer.
Time Complexity

O(N^3), where N is the size of the string.

 

We are generating all the substring in O(N^2) complexity and for every substring, one traversal will be required to check the number of distinct characters.

Space Complexity

O(1).

 

We are using constant extra space.

Code Solution
(100% EXP penalty)
Longest Sub-string with at most K Distinct Characters
All tags
Sort by
Search icon

Interview problems

3 approaches : Brut, Better Optimal

import java.util.HashMap;

import java.util.HashSet;




public class Solution {

    public static int getLengthofLongestSubstring(int k, String s) {

        // Write your code here.

        return slidingWindowApproach(k, s);

    }




    public static int brutforceApproach(int k, String s) {

        // Write your code here.

        int ans = 0, n = s.length();




        for (int i = 0; i < n; i++) {

            for (int j = i; j < n; j++) {

                // i to j is a subarray

                HashSet<Character> set = new HashSet<>();

                int count = 0;




                for (int l = i; l <= j; l++) {

                    char c = s.charAt(l);

                    set.add(c);

                    count++;

                }




                if (set.size() <= k) {

                    ans = Math.max(ans, count);

                }

            }

        }




        return ans;

    }




    public static int betterApproach(int k, String s) {

        int n = s.length(), ans = 0;




        for (int i = 0; i < n; i++) {

            int j = i;

            HashSet<Character> set = new HashSet<>();




            while (j < n) {

                set.add(s.charAt(j));




                if (set.size() <= k) {

                    ans = Math.max(ans, j - i + 1);

                }




                j++;

            }

        }




        return ans;

    }




    public static int slidingWindowApproach(int k, String s) {

        int i = 0, j = 0, n = s.length(), ans = 0;

        HashMap<Character, Integer> map = new HashMap<>();




        while (j < n) {

            char c = s.charAt(j);




            while (map.size() > k) {

                char temp = s.charAt(i);

                map.put(temp, map.getOrDefault(temp, 0) - 1);




                if (map.get(temp) <= 0) {

                    map.remove(temp);

                }




                i++;

            }




            map.put(c, map.getOrDefault(c, 0) + 1);

            

            if (map.size() <= k) {

                ans = Math.max(ans, j - i + 1);

            }

            

            j++;

        }




        return ans;

    }

}


3 views
0 replies
0 upvotes

Interview problems

Brute and Optimal Both (80/80) passed using cpp

#include<bits/stdc++.h>
int getLengthofLongestSubstring(int k, string s)
{
   // Write your code here.
   //brute force approach
   // for(int i=0;i<s.size();i++){
   //    unordered_set<int> stt;
   //    for(int j=i;j<s.size();j++){
   //       stt.insert(s[j]);
   //       if(stt.size()<=k){
   //          maxLen = max(maxLen,j-i+1);
   //       }
   //       else break;
   //    }
   // }
   int maxLen = 0;
   int r=0,l=0;
   int n= s.size();
   unordered_map<char,int> mpp;
   while(r<=n-1){
      mpp[s[r]]++;    
      if(mpp.size()>k){
            mpp[s[l]]--;
            if(mpp[s[l]]==0) mpp.erase(s[l]);
            l = l+1;
         }
      if(mpp.size()<=k)
         maxLen = max(maxLen,r-l+1);
      r++;
     
   }
   return maxLen;
}
//kindly upvote, it helps me motivated and help you
//if this helped you in any way I'm glad

//Thanks in advance
54 views
0 replies
0 upvotes

Interview problems

Java

import java.util.HashMap;
import java.util.Map;

public class Solution {
	public static int getLengthofLongestSubstring(int K, String s) {
		Map<Character,Integer> countMap = new HashMap<>();
		int i=0,j=0;
		int maxi = 1;

		while(j < s.length()){
			Character charAtJ = s.charAt(j);
			countMap.put(charAtJ, countMap.getOrDefault(charAtJ, 0) + 1);

			if(countMap.size() == K){
				maxi = Math.max(maxi, j - i + 1);
			}
			else if(countMap.size() > K){
				while(countMap.size() > K){
					countMap.put(s.charAt(i), countMap.get(s.charAt(i)) - 1);
					if(countMap.get(s.charAt(i)) == 0){
						countMap.remove(s.charAt(i));
					}
					i++;
				}
				
			}
			j++;
		}

		return maxi;

	}
}
64 views
0 replies
0 upvotes

Interview problems

Java ~ Sliding Window Approch

import java.util.HashMap;

public class Solution {
	public static int getLengthofLongestSubstring(int k, String s) {
		// Write your code here.
		HashMap<Character,Integer> map = new HashMap<>();
		int start =0;
		int end=0;
		int ans=1;
		while(end<s.length()){
			char ch =s.charAt(end);
			map.put(ch,map.getOrDefault(ch, 0)+1);
			if(map.size()<k){
				end++;
			}
			else if(map.size()==k){
				ans=Math.max(end-start+1,ans);
				end++;
			}else{
				while(map.size()>k){
					char ss =s.charAt(start);
					map.put(ss, map.get(ss)-1);
					if(map.get(ss)==0){
						map.remove(ss);
					}
					start++;
				}
				end++;
			}
		}
		return ans;
	}
}

java

57 views
0 replies
1 upvote

Interview problems

5 liner Code | most concise Sliding Window

#include<bits/stdc++.h>
int getLengthofLongestSubstring(int k, string s){
   int n = s.size() , maxLen = 0;
   vector<int> freq(26,0);
   for(int i=0,j=0,distinct=0;j<n;j++){
      distinct += (freq[s[j]-'a']++ == 0);
      while(distinct > k) distinct -= (--freq[s[i++]-'a'] == 0);
      maxLen = max(maxLen,j-i+1);
   }
   return maxLen;
}
191 views
0 replies
0 upvotes

Interview problems

whats wrong with my code

#include<bits/stdc++.h>

int getLengthofLongestSubstring(int k, string s)
{
   // Write your code here.
   int op = 0;
   int start = 0;
   map<int,int> m;
   int distinct = 0;
   

   for(int pointer = 0;s[pointer]!='\0';pointer++){

     
      if(m[s[pointer]-'a']==0){
         distinct++;
      }

       m[s[pointer]-'a']++;

      if(distinct > k){
         int tempStart = start;
        while(tempStart<pointer && m[s[start]-'a']>0){
           m[s[tempStart]-'a']--;
           tempStart++;
        }
       
        distinct-=1;
        start = tempStart;
         
      }

      
      op = max(op,pointer-start+1);

   }



   return op;


}
127 views
0 replies
0 upvotes

Interview problems

Short and Simple | Sliding Window Solution

#include<bits/stdc++.h>
int getLengthofLongestSubstring(int k, string s)
{

    
      unordered_map<char,int> m ;
    int i = 0 , j = 0 , n = s.length();
    int len = 0 ;
    while(j < n)
    {
        m[s[j]]++;
        while(m.size() > k)
        {
            m[s[i]]--;
            if(m[s[i]] == 0)
                m.erase(s[i]);
            i++;
        }
        len = max(len , j - i + 1);
        j++;
        
    }
    
    return len ;
    
    
}

beginners

programming

223 views
1 reply
0 upvotes

Interview problems

Longest Substring with at most K distinct Char

#include<bits/stdc++.h>
int getLengthofLongestSubstring(int k, string s)
{
    
   unordered_map<char,int>mp;
    int i=0;
    int j=0;
    int n=s.length();
    int len=0;
    if(k>n)return 1;
    while(j<n)
    {
        mp[s[j]]++;
        if(mp.size()==k)
            len=max(len,j-i+1);
        else if(mp.size()>k)
        {
            while(mp.size()>k)
            {
                mp[s[i]]--;
                if(mp[s[i]]==0)
                    mp.erase(s[i]);
                 i++;
                 if(mp.size()==k)
                    len=max(len,j-i+1);
            }
        }
        j++;
    }
    return len;
}

Longest Sub-string with at most K Distinct Characters

176 views
0 replies
0 upvotes

Interview problems

Discussion thread on Interview Problem | Longest Sub-string with at most K Distinct Characters

Hey everyone, creating this thread to discuss the interview problem - Longest Sub-string with at most K Distinct Characters.

 

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Longest Sub-string with at most K Distinct Characters

 

136 views
3 replies
0 upvotes
Full screen
Console