Longest Substring with At Least K Repeating Characters LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Bloomberg ByteDance Facebook Google Microsoft UberViews 2991

Problem Statement

The problem Longest Substring with At Least K Repeating Characters LeetCode Solution says 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 for Longest Substring with At Least K Repeating Characters:

Test Case 1:

Input:

S = “aaabbcddaeaaff”

k = 2

Output:

5

Test Case 2:

Input:

S = “abcbaac”

k = 3

Output:

0

Explanation for Longest Substring with At Least K Repeating Characters:

i) For the first test case, in the substring “aaabb” every character occurs at least 2 times. So the output is 5.

ii) For the second test case, there is no substring where every character occurs at least 3 times. So the output is 0.

Approach

Idea:

From the question, we can think that if a character is having a frequency less than k, then it can never be part of the resultant string. So we can split the input string into several smaller strings around those characters which will reduce our input size and it will be easier to compute the output. Here ‘c’ and ‘e’  are such characters.Longest Substring with At Least K Repeating Characters LeetCode Solution

We can keep track of the frequencies of the characters in an array. There might be a case where each and every character has a frequency >= k. In that case, we need to return the length of the string.

Code

Java Program for Longest Substring with At Least K Repeating Characters LeetCode Solution

class Solution {
    public int longestSubstring(String S, int k) {
        int charFrequency[] = new int[26];
        char[] strArray = S.toCharArray();
        for(char ch: strArray){
            int index = ch -'a';
            charFrequency[index]++;
        }

        boolean valid = true;

        int start =0;
        int maxLen = 0;
        for(int index = 0;index < S.length();index++) {
            if(charFrequency[strArray[index] - 'a'] >0 && charFrequency[strArray[index] - 'a'] <k ){
                String subString = S.substring(start, index);
                maxLen  = Math.max(maxLen , longestSubstring(subString, k));
                start = index+1;
                valid = false;
            }
        }

        if(valid){
            return S.length();
        } else{
            return Math.max(maxLen, longestSubstring(S.substring(start), k));
        }
    }
}

C++ Program for Longest Substring with At Least K Repeating Characters LeetCode Solution

class Solution {
public:
    int longestSubstring(string S, int k) {
        int len = S.size();
        if(len == 0 || len < k) 
          return 0;
        if(k <= 1) 
          return len;

        unordered_map<char, int> charFrequency;
        for(char ch: S) 
          charFrequency[ch] += 1;

        int left = 0;
        while(left < len && charFrequency[S[left]] >= k) 
          left++;
        if(left >= len-1) 
          return left;

        int lengthString1 = longestSubstring(S.substr(0, left), k);
        while(left < len && charFrequency[S[left]] < k) 
          left++;
        int lengthString2 = (left < len) ? longestSubstring(S.substr(left), k) : 0;
        return max(lengthString1, lengthString2);
    }
};

Complexity Analysis for Longest Substring with At Least K Repeating Characters LeetCode Solution

Time Complexity

Here we are iterating the string and generating substring. So in the worst-case time complexity is O(n^2).

Space Complexity

We are using an array of 26 lengths to store the frequency. But it can be considered as constant. So the space complexity can be considered as O(1).

Reference: https://en.wikipedia.org/wiki/Substring

Translate »