LeetCode 395: Longest Substring with At Least K Repeating Characters Solution in Python – A Step-by-Step Guide

What Is LeetCode 395: Longest Substring with At Least K Repeating Characters?

LeetCode 395: Longest Substring with At Least K Repeating Characters provides a string s and an integer k, and your task is to return the length of the longest substring where each character appears at least k times. It’s a problem that tests your ability to manage character frequencies and substring boundaries efficiently!

Problem Statement

• Input:
• s: String of lowercase letters.
• k: Integer representing minimum frequency.
• Output: Integer - Length of the longest valid substring, or 0 if none.
• Rules:
• Every character in the substring must appear ≥ k times.
• Substring can be any contiguous segment of s.

Constraints

• 1 <= s.length <= 10⁴
• 1 <= k <= 10⁵
• s contains only lowercase English letters.

Examples

• Input: s = "aaabb", k = 3
• Output: 3
• "aaa" (indices 0-2), each char ≥ 3.
• Input: s = "ababbc", k = 2
• Output: 5
• "ababb" (indices 0-4), 'a': 2, 'b': 3.
• Input: s = "aaabbb", k = 3
• Output: 6
• "aaabbb", 'a': 3, 'b': 3.

These show the frequency puzzle—let’s solve it!

Understanding the Problem: Finding the Longest Valid Substring

To tackle LeetCode 395 in Python, we need to: 1. Find a substring where every character has frequency ≥ k. 2. Maximize its length. 3. Handle efficiently given string length and k constraints.

A naive approach might check all substrings, but that’s O(n³). We’ll use:

• Best Solution: Divide and conquer—O(n log n) time, O(n) space—fast and optimal.
• Alternative Solution: Sliding window with counting—O(n²) time, O(n) space—intuitive but slower.

Let’s conquer with the best solution!

Best Solution: Divide and Conquer

Why This Is the Best Solution

The divide and conquer approach runs in O(n log n) time with O(n) space by recursively splitting the string at characters with frequency < k, solving subproblems efficiently. It’s the most efficient—avoiding brute-force substring checks and leveraging the insight that invalid characters must split valid segments!

How It Works

Think of it like pruning a tree:

• Insight: In a valid substring, every char has freq ≥ k. If a char has freq < k, it can’t be part of the answer—split there.
• Process:
• Count frequencies in current segment.
• Find a char with freq < k (split char).
• Split string at all occurrences of split char.
• Recurse on each resulting substring.
• Base: If all chars have freq ≥ k, return length.
• Result: Max length from all subproblems.

It’s like dividing until all pieces fit!

Step-by-Step Example

For s = "aaabb", k = 3:

• Count: {'a': 3, 'b': 2}.
• Split: 'b' < 3, split at 'b'.
• Substrings: "aaa", "b".
• Recurse:
• "aaa": {'a': 3} → All ≥ 3, return 3.
• "b": {'b': 1} < 3, return 0.
• Result: max(3, 0) = 3.

For s = "ababbc", k = 2:

• Count: {'a': 2, 'b': 3, 'c': 1}.
• Split: 'c' < 2, split at 'c'.
• Substrings: "ababb", "".
• Recurse:
• "ababb": {'a': 2, 'b': 3} → All ≥ 2, return 5.
• "": return 0.
• Result: max(5, 0) = 5.

For s = "aaabbb", k = 3:

• Count: {'a': 3, 'b': 3} → All ≥ 3, return 6.

Code with Explanation

Here’s the Python code using divide and conquer:

Copy codeclass Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        # Base case: string too short
        if len(s) < k:
            return 0

        # Count frequencies
        count = {}
        for char in s:
            count[char] = count.get(char, 0) + 1

        # Find split character (freq < k)
        split_char = None
        for char, freq in count.items():
            if freq < k:
                split_char = char
                break

        # If no split char, all chars meet k
        if split_char is None:
            return len(s)

        # Split and recurse
        max_len = 0
        for substring in s.split(split_char):
            max_len = max(max_len, self.longestSubstring(substring, k))

        return max_len

Explanation

• Lines 4-5: If len(s) < k, no valid substring—O(1).
• Lines 7-9: Count frequencies—O(n).
• Lines 11-15: Find split char with freq < k—O(1) (26 letters).
• Lines 17-18: If no split char, all ≥ k, return length—O(1).
• Lines 20-23: Split at split_char, recurse, take max—O(n) splits, O(log n) depth.
• Time: O(n log n)—n for counting/splitting, log n recursion depth.
• Space: O(n)—recursion stack and split substrings.

This is like a string splitter—fast and smart!

Alternative Solution: Sliding Window with Counting

Why an Alternative Approach?

The sliding window with counting solution runs in O(n²) time with O(n) space by trying all possible window sizes and checking frequencies. It’s less efficient—great for understanding a window-based approach, but slower and more complex than divide and conquer for this problem!

How It Works

• Window: Try all start-end pairs.
• Count: Check frequencies within window.
• Validate: All chars ≥ k.
• Result: Max valid window length.

Step-by-Step Example

For s = "aaabb", k = 3:

• Windows:
• "aaa": {'a': 3} → 3.
• "aaab": {'a': 3, 'b': 1} → Invalid.
• "aaabb": {'a': 3, 'b': 2} → Invalid.
• Result: 3.

Code with Explanation

Copy codeclass Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if len(s) < k:
            return 0

        max_len = 0
        # Try all substrings
        for i in range(len(s)):
            count = {}
            for j in range(i, len(s)):
                count[s[j]] = count.get(s[j], 0) + 1
                # Check if valid
                if all(freq >= k for freq in count.values()):
                    max_len = max(max_len, j - i + 1)

        return max_len

Explanation

• Lines 4-5: If len(s) < k, return 0—O(1).
• Lines 7-14: Nested loops:
• Outer: Start index i—O(n).
• Inner: End index j, count freqs—O(n).
• Check all ≥ k—O(1) per window (26 letters).
• Line 15: Return max length—O(1).
• Time: O(n²)—n windows, O(n) counting.
• Space: O(n)—count dict.

It’s a window checker—clear but slow!

Comparing the Two Solutions

• Divide and Conquer (Best):
• Time: O(n log n)—logarithmic splits.
• Space: O(n)—stack.
• Pros: Fast, scalable, elegant.
• Cons: Recursive logic.
• Sliding Window (Alternative):
• Time: O(n²)—quadratic.
• Space: O(n)—dict.
• Pros: Intuitive windowing.
• Cons: Slow, inefficient.

Divide and conquer wins for speed and efficiency!

Additional Examples and Edge Cases

• s="a", k=2: Both return 0.
• s="aaa", k=3: Both return 3.
• Large k: Divide and conquer scales better.

Divide and conquer is optimal, sliding window works too.

Complexity Breakdown

• Divide and Conquer:
• Time: O(n log n).
• Space: O(n).
• Sliding Window:
• Time: O(n²).
• Space: O(n).

Divide and conquer excels for performance.

Key Takeaways

• Divide and Conquer: Split and solve—fast and smart!
• Sliding Window: Count and check—clear but slow!
• Substrings: Patterns beat brute force.
• Python Tip: Recursion rocks—see [Python Basics](/python/basics).

Final Thoughts: Find That Substring

LeetCode 395: Longest Substring with At Least K Repeating Characters in Python is a frequency challenge. Divide and conquer is the efficiency champ, while sliding window offers a tangible alternative for small cases. Want more? Try LeetCode 3: Longest Substring Without Repeating Characters or LeetCode 76: Minimum Window Substring. Ready to count? Visit Solve LeetCode 395 on LeetCode and find that substring today!