Longest Substring With At Least K Repeating Characters

Solution For Longest Substring With At Least K Repeating Characters

Problem Statement:

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

Example 1:

Input: s = “aaabb”, k = 3
Output: 3
Explanation: The longest substring is “aaa”, as ‘a’ is repeated 3 times.

Example 2:

Input: s = “ababbc”, k = 2
Output: 5
Explanation: The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.

Approach:

The problem is to find the longest substring with at least k repeating characters in a given string. We can use the brute-force approach to solve this problem by considering all possible substrings of the string and count the frequency of each character in the substring. However, this approach is not efficient, and it will take a lot of time to find the result for a large-sized string.

An efficient approach to solve this problem is to use a divide and conquer approach, which involves specifically splitting the input string into substrings. First, we need to count the frequency of all characters in the given string. Then we will divide the string into substrings whenever we encounter a character whose frequency is less than k. We will then recursively apply the same procedure to these substrings. Finally, we will return the length of the longest substring that fulfills the condition that the frequency of each character is greater than or equal to k.

Algorithm:

  1. initialize an array ‘freq’ of size 26, and initialize all its elements to zero.
  2. count the frequency of each character in the given string and store it in the ‘freq’ array.
  3. for each character of the given string
    a. if the frequency of the character is less than k
    i. divide the string into substrings at the current index
    – all the substrings obtained in this way will contain fewer than k occurrences of the current character
    ii. recursively apply the same procedure to these substrings
  4. if all characters in the substring have frequency greater than or equal to k, return the length of the substring.
    else return 0.

Time Complexity:

The Time complexity for this algorithm is O(n log n), where ‘n’ is the length of the string. The time complexity of the divide and conquer algorithm is O(n log n) because the string is divided into smaller substrings and the process is repeated recursively.

Space Complexity:

The space complexity for this algorithm is O(1). We are using a fixed amount of space to store the frequency of each character. However, if we use a hash map to count the frequency, the space complexity will increase to O(n).

Code:

class Solution {
public:
int longestSubstring(string s, int k) {
int n = s.size();
if(n == 0 || n < k) return 0;
if(k == 1) return n;
int freq[26] = {0};
for(int i = 0; i < n; i++) freq[s[i]-‘a’]++;
int i = 0;
while(i < n && freq[s[i]-‘a’] >= k) i++;
if(i == n) return n;
int left = longestSubstring(s.substr(0, i), k);
while(i < n && freq[s[i]-‘a’] < k) i++;
int right = longestSubstring(s.substr(i), k);
return max(left, right);
}
};

Explanation:

In this implementation, we have used the divide and conquer approach to solve the problem. We have taken a string ‘s’ and an integer ‘k’ as input. We first check if the size of the string is 0 or less than k. If it is, then we return 0 as there is no substring of length k in the given string. If k is 1, then the entire string is the substring with at least k repeating characters, so we return the size of the string.

We initialize an array ‘freq’ of size 26, and initialize all its elements to zero. We then count the frequency of each character in the given string and store it in the ‘freq’ array.

We then traverse the string and check if the frequency of the current character is less than k. If it is, we split the string at the current index by calling the ‘substr’ function and recursively apply the same procedure to the resulting substrings.

If all characters in the substring have frequency greater than or equal to k, we return the length of the substring. Otherwise, we return 0.

In this code, we have used a recursive function ‘longestSubstring’ to implement the divide and conquer approach. The function takes a string ‘s’ and an integer ‘k’ as input and returns the length of the longest substring having at least k repeating characters.

In the function, we first check if the size of the string is 0 or less than k. If it is, then we return 0 as there is no substring of length k in the given string. If k is 1, then the entire string is the substring with at least k repeating characters, so we return the size of the string.

We then check if all characters in the given string have frequency greater than or equal to k. If it is, we return the size of the string.

If all characters in the string do not have frequency greater than or equal to k, we find the first character whose frequency is less than k and split the string at that point using the ‘substr’ function. We then recursively apply the same procedure to the resulting substrings.

Finally, we return the maximum length of the substrings returned by the recursive calls.

Conclusion:

In this problem, we have calculated the length of the longest substring having at least k repeating characters in a given string using a divide and conquer approach. We have used the frequency of characters to divide the string into smaller substrings and recursively applied the same procedure to these substrings. The time complexity of this algorithm is O(n log n), and the space complexity is O(1).

Step by Step Implementation For Longest Substring With At Least K Repeating Characters

public int longestSubstring(String s, int k) {
        int n = s.length();
        if (n == 0 || k > n) return 0;
        if (k == 1) return n;
        
        int[] count = new int[26];
        for (int i = 0; i < n; i++) {
            count[s.charAt(i) - 'a']++;
        }
        
        int max = 0;
        for (int i = 0; i < n; i++) {
            int j = i;
            while (j < n && count[s.charAt(j) - 'a'] >= k) {
                j++;
            }
            if (j == n) {
                return n;
            }
            int m = longestSubstring(s.substring(i, j), k);
            if (m > max) {
                max = m;
            }
            i = j;
        }
        return max;
    }
def longestSubstring(s, k): 
    
    # Base case 
    if len(s) < k: 
        return 0
    
    # Dictionary to store count of characters in a string 
    ctr = collections.Counter(s) 
    
    # To store length of longest substring with 
    # at least k repeating characters 
    res = 0
    
    for i in ctr.keys(): 
        
        # If character occurs less than k times, 
        # it cannot be a part of the longest 
        # substring 
        if ctr[i] < k: 
            
            # Splitting the string at the occurrence 
            # of character with count less than k 
            for j in range(len(s)): 
                if s[j] == i: 
                    before = longestSubstring(s[ : j], k) 
                    after = longestSubstring(s[j+1 : ], k) 
                    
                    # Updating maximum length substring 
                    res = max(res, before, after) 
            
            # Returning result 
            return res 
    
    # If all characters satisfy the condition, 
    # return the length of whole string 
    return len(s)
var longestSubstring = function(s, k) {
    // edge case: if string is empty, return 0
    if (s === "") {
        return 0;
    }
    
    // create hashmap to store frequencies of each character
    // key: character
    // value: frequency
    let charFreq = {};
    for (let i = 0; i < s.length; i++) {
        let char = s[i];
        if (charFreq[char]) {
            charFreq[char]++;
        } else {
            charFreq[char] = 1;
        }
    }
    
    // edge case: if all characters satisfy k, return string length
    let allValid = true;
    for (let key in charFreq) {
        if (charFreq[key] < k) {
            allValid = false;
            break;
        }
    }
    if (allValid) {
        return s.length;
    }
    
    // otherwise, recurse on substrings formed by splitting on invalid characters
    let maxLen = 0;
    let start = 0;
    for (let i = 0; i < s.length; i++) {
        let char = s[i];
        // if current character is invalid, update maxLen and start of next substring
        if (charFreq[char] < k) {
            maxLen = Math.max(maxLen, longestSubstring(s.substring(start, i), k));
            start = i + 1;
        }
    }
    
    // update maxLen for final substring
    return Math.max(maxLen, longestSubstring(s.substring(start), k));
};
class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.length();
        if (n == 0 || k > n) return 0;
        if (k == 0) return n;
        
        int max_len = 1;
        for (int i = 1; i <= 26; i++) {  // try all possible number of unique characters
            int start = 0, cur_len = 0, unique = 0, no_less_than_k = 0;
            vector counts(26, 0);
            for (int j = 0; j < n; j++) {
                if (counts[s[j]-'a'] == 0) unique++;
                counts[s[j]-'a']++;
                if (counts[s[j]-'a'] == k) no_less_than_k++;
                while (unique > i) {
                    counts[s[start]-'a']--;
                    if (counts[s[start]-'a'] == 0) unique--;
                    if (counts[s[start]-'a'] == k-1) no_less_than_k--;
                    start++;
                }
                if (unique == i && no_less_than_k == i) {
                    cur_len = j-start+1;
                    max_len = max(max_len, cur_len);
                }
            }
        }
        return max_len;
    }
};
using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 

namespace ConsoleApplication1 
{ 
    class Program 
    { 
        static void Main(string[] args) 
        { 
            string s = "aaabb"; 
            int k = 3; 

            int result = LongestSubstring(s, k); 

            Console.WriteLine(result); 
            Console.ReadLine(); 
        } 

        public static int LongestSubstring(string s, int k) 
        { 
            int max = 0; 

            for (int i = 0; i < s.Length; i++) 
            { 
                int[] count = new int[26]; 
                int currMax = 0; 
                int currStart = i; 
                int unique = 0; 
                int noLessThanK = 0; 

                for (int j = i; j < s.Length; j++) 
                { 
                    if (count[s[j] - 'a'] == 0) 
                    { 
                        unique++; 
                    } 
                    count[s[j] - 'a']++; 
                    if (count[s[j] - 'a'] == k) 
                    { 
                        noLessThanK++; 
                    } 

                    if (unique == noLessThanK) 
                    { 
                        currMax = j - currStart + 1; 
                        if (currMax > max) 
                        { 
                            max = currMax; 
                        } 
                    } 
                } 
            } 

            return max; 
        } 
    } 
}


Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]