LeetCode 395: Longest Substring with At Least K Repeating Characters Solution

Master LeetCode problem 395 (Longest Substring with At Least K Repeating Characters), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

395. Longest Substring with At Least K Repeating Characters

Medium

Hash Table String Divide and Conquer Sliding Window

Problem Explanation

Explanation

To solve this problem, we can use a divide and conquer approach. We can iterate through the string and find the count of each character. Then, we can divide the string based on characters with count less than k. We recursively apply the same logic on the divided substrings until all characters in a substring have count >= k. The maximum length of such substrings will be our answer.

Count the frequency of each character in the string.
Find the index of the first character with count less than k.
If all characters in the string have count >= k, return the length of the string.
Otherwise, recursively apply the same logic on the substrings before and after the character with count less than k.

Time complexity: O(n * log n) where n is the length of the string. Space complexity: O(n) for the recursive stack.

Solution Code

class Solution {
    public int longestSubstring(String s, int k) {
        return longestSubstringHelper(s, k, 0, s.length());
    }
    
    private int longestSubstringHelper(String s, int k, int start, int end) {
        if (end - start < k) return 0;
        
        int[] count = new int[26];
        for (int i = start; i < end; i++) {
            count[s.charAt(i) - 'a']++;
        }
        
        for (int i = start; i < end; i++) {
            if (count[s.charAt(i) - 'a'] < k) {
                int left = longestSubstringHelper(s, k, start, i);
                int right = longestSubstringHelper(s, k, i + 1, end);
                return Math.max(left, right);
            }
        }
        
        return end - start;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 395 (Longest Substring with At Least K Repeating Characters)?

This page provides optimized solutions for LeetCode problem 395 (Longest Substring with At Least K Repeating Characters) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 395 (Longest Substring with At Least K Repeating Characters)?

The time complexity for LeetCode 395 (Longest Substring with At Least K Repeating Characters) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 395 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 395 in Java, C++, or Python.

Back to LeetCode Solutions