Longest Substring with At Least K Repeating Characters

Efficient Approach

If we want to build up an efficient solution, we will need to find out if there is any redundancy or any repetition that we are doing. The redundancy in our code is that we check for every substring of the string s if the condition is satisfied. We can make some observations that we can infer to get rid of the extra redundant computation.

Notice that the thing of prime importance is that we must have unique characters in the substrings, which has a count of each unique character >= k. The substring which follows this condition, then we should maximize our answer. In the naive approach, what we did was going through substring of every length. The substring could have any number of unique characters with frequency >= k; obviously, it should not be greater than the total size of the string s.

So the point we are trying to make here is that instead of focusing on lengths, let’s give prime importance to the number of unique characters in the substring and try to find the substring with a given number of unique characters in the substring and count of the unique characters is >=k. If we get such strings, we can easily maximize our answer.

NOTE: we are not trying to say that the substring with a greater number of unique characters will contain the count of each unique character >=k. 

We thought of giving importance to the number of unique characters in the substring because the number of unique characters in any string <= 26(as only lower case letters are allowed). Then we can find only the substring with the frequency of each unique character >=k. 

Let’s also look at the given example in the problem statement and understand the idea.

Now let’s look at substrings with L number of unique characters where L can take values from {1, 2, 3}For each substring with exactly L unique characters, we can look for the substrings with the frequency of each unique character >= k.  

Let’s look at how we find the substrings with L = 2 unique characters such that the condition is satisfied. We iterate through the string in a sliding window fashion. 

Since the number of unique characters is 1 we can extend the window.

Since the number of unique characters is 2, but the frequency condition is not satisfied, we can extend the window.

Since the number of unique characters is 2, but the frequency condition is not satisfied, we can extend the window.

Since the number of unique characters is 2 and the frequency condition is satisfied, we can still extend the window to maximize our answer, but locally we can update our answer from 0 to 4.

Since the number of unique characters is 3, we will shrink the window and drop the starting character of the window. 

To save time, we can drop the next 2 characters at the front of the window because they will still exceed the unique characters.

Now the number of unique characters is 2, but the frequency condition is not met. Now we can increase the window size.

Now the number of unique characters is 2, but the frequency condition is not met. We can’t increase the window size further; hence for L = 2, we got the maximum length = 4.

Now, you can try dry running for L =1, 3 also, and you will find the optimal answer we get is for L = 3, i.e., 6. 

Let’s look at the Code.

Implementation in C++

//C++ program to solve the problem Longest Substring with At Least K Repeating //Characters
#include <bits/stdc++.h>
using namespace std;

int longestSubstring(string &s, int k){
    //maintain a count map to store the count of unique characters 
    vector<int> countMap(26, 0);
    int maximumUniqueChars = 0; // variable that stores the maximum number of unique characters
    for(char c:s) 
        countMap[c-'a']++;
    for(int i=0;i<26;++i)
        if(countMap[i]>0)
            maximumUniqueChars++;
    int ans = 0; // final answer that would be returned
    
    // iterate over number of unique characters in a substring
    for (int currUnique = 1; currUnique <= maximumUniqueChars; currUnique++) {
        // fill countMap with 0
        fill(countMap.begin(), countMap.end(), 0);
        int l = 0, r = 0; // l, r  for representing a window[l,r]
        int countAtLeastK = 0; // number of unique characters in the window with freq >= k.  
        int unique = 0; // numberof unique characters in the window
        
        // start iterating over the window
        while (r < s.size()) {
            if(countMap[s[r]-'a']==0) unique++; // increment the count of unique character
            countMap[s[r]-'a']++; // increment the count of current character
            if(countMap[s[r]-'a']==k) countAtLeastK++; // increment if freq == k
            
            // if number of unique characters are more start shrinking the window
            if(unique>currUnique){ 
                //shrinking the window
                while(l<r and unique>currUnique){
                    countMap[s[l]-'a']--; // decrement the count
                    if(countMap[s[l]-'a']==0){
                        unique--;        // reduce the number of unique characters
                    }
                    l++;
                }
                int countKfreqchars = 0;
                for(int i=0;i<26;++i) if(countMap[i]>=k) countKfreqchars++;
                countAtLeastK = countKfreqchars; // update the count of unique chars with freq>=k
            }
            //update the answer if the condition is satisfied
            if(unique == currUnique and countAtLeastK==unique){
                ans = max(ans, r-l+1);
            }
            // increment the window size
            r++;
        }
        // finally check if the condition is satisfied
        if(unique == currUnique and countAtLeastK==unique){
            ans = max(ans, r-l);
        }
    }
    return ans;
}

int main() {
    // string s
	string s = "ababcc";
	// k
	int k = 2;

	//find the answer
	cout<<"The longest substring having atleast k frequency of each unique character is: "<<longestSubstring(s, k);
	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

The longest substring having atleast k frequency of each unique character is: 6

Complexity Analysis

Time Complexity: O(|s|*26)

We are traversing the whole string s maximum unique character times <= 26 in the worst case.

Space complexity: O(1) as we are using constant memory to store the count of characters.

Hence we reached an efficient solution from a quadratic solution. 

Frequently Asked Questions

Q1. When is the Sliding window technique useful?                                                        

Answer) The sliding window technique is useful when you need to keep track of a contiguous sequence of elements.

Q2. Why is hashing important?                                                                               

Answer) Hashing is very useful and important because it helps store key-value pairs, increasing the solution’s efficiency and providing fast checks.  

Q3. How often are strings asked in interviews?                                                                                    

Answer) String is a favorite topic of the top companies, including Apple, Google, Amazon, etc. It is often asked in interviews and questions formed on strings, usually club 2-3 essential concepts as discussed in the blog. 

Key Takeaways

This article taught us how to find the Longest Substring with At Least K Repeating Characters. We also saw how to approach the problem using a naive approach followed by an efficient solution. We discussed an iterative implementation using examples, pseudocode, and proper code in detail.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out how we can apply hashing in strings and the sliding window technique to simplify our task and make fewer comparisons. 
Check out this problem - Longest String Chain

Now, we recommend you practice problem sets based on the concepts of finding the Longest Substring with At Least K Repeating Characters to master your fundamentals. You can get a wide range of questions similar to the problem of finding the Longest Substring with At Least K Repeating Characters on Coding Ninjas Studio. 

Happy Learning!!!