Last updated on January 5th, 2025 at 01:19 am

Here, we see Longest Substring with At Least K Repeating Characters LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.

List of all LeetCode Solution

Topics

String

Companies

Baidu

Level of Question

Medium

Longest Substring with At Least K Repeating Characters LeetCode Solution

1. 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.

if no such substring exists, return 0.

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.

2. Coding Pattern Used in Solution

The coding pattern used in all the provided implementations is “Divide and Conquer”. The problem is broken into smaller subproblems by dividing the string into substrings based on characters that do not meet the frequency condition (< k). Each substring is then recursively processed to find the longest valid substring. Additionally, the Sliding Window pattern is used in the JavaScript implementation to optimize the search for substrings with a specific number of unique characters.

3. Code Implementation in Different Languages

3.1 Longest Substring with At Least K Repeating Characters C++

class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.length();
        if(n == 0 or n < k) return 0;
        if(k <= 1) return n;
        unordered_map<char,int> countMap;
        for(char c : s) countMap[c]++;
        int left =0;
        while(left < n && countMap[s[left]] >= k) left++;
        if(left >= n-1) return left;
        int l1 = longestSubstring(s.substr(0,left) ,k);
        while(left < n && countMap[s[left]] < k) left++;
        int l2 = left < n ? longestSubstring(s.substr(left),k) : 0;
        return max(l1,l2);
    }
};

3.2 Longest Substring with At Least K Repeating Characters Java

class Solution {
    public int longestSubstring(String s, int k) {
        if (s == null || s.length() == 0) return 0;
        char[] chars = new char[26];
        for (int i = 0; i < s.length(); i += 1) chars[s.charAt(i) - 'a'] += 1;
        boolean flag = true;
        for (int i = 0; i < chars.length; i += 1) {
            if (chars[i] < k && chars[i] > 0) flag = false;
        }
        if (flag == true) return s.length();
        int result = 0;
        int start = 0, cur = 0;
        while (cur < s.length()) {
            if (chars[s.charAt(cur) - 'a'] < k) {
                result = Math.max(result, longestSubstring(s.substring(start, cur), k));
                start = cur + 1;
            }
            cur++;
        }
        result = Math.max(result, longestSubstring(s.substring(start), k));
        return result;
    }
}

3.3 Longest Substring with At Least K Repeating Characters JavaScript

var longestSubstring = function(s, k) {
    let maxUnique = new Set(s).size;
    let max = 0;
    for (let curUnique = 1; curUnique <= maxUnique; curUnique++) {
        let start = 0, end = 0, atLeastK = 0, unique = 0, m = new Map();
        while (end < s.length) {    
            m.set(s[end], m.get(s[end]) + 1 || 1);
            if (m.get(s[end]) == 1) unique++;
            if (m.get(s[end]) == k) atLeastK++;
            while (unique > curUnique) {
                m.set(s[start], m.get(s[start]) - 1);
                if (m.get(s[start]) == k-1) atLeastK--;
                if (m.get(s[start]) == 0) unique--;
                start++;
            }
            if (unique == curUnique && unique == atLeastK) {
                max = Math.max(max, end - start + 1);
            } 
            end++;
        }
    }
    return max;
};

3.4 Longest Substring with At Least K Repeating Characters Python

class Solution(object):
    def longestSubstring(self, s, k):
        cnt = collections.Counter(s)
        st = 0
        maxst = 0
        for i, c in enumerate(s):
            if cnt[c] < k:
                maxst = max(maxst, self.longestSubstring(s[st:i], k))
                st = i + 1
        return len(s) if st == 0 else max(maxst, self.longestSubstring(s[st:], k))

4. Time and Space Complexity

	Time Complexity	Space Complexity
C++	O(n²)	O(n)
Java	O(n²)	O(n)
JavaScript	*O(n 26)**	O(n)
Python	O(n²)	O(n)

The Divide and Conquer pattern is the primary approach used in all implementations.
The Sliding Window pattern is additionally used in the JavaScript implementation for optimization.
The time complexity is O(n^2) for C++, Java, and Python due to substring creation, while JavaScript achieves O(n) in practice due to the sliding window approach.
The space complexity is O(n) for all implementations due to recursion and auxiliary data structures.