Understanding the Problem

You are given a string s and an integer k.
You must find the length of the longest substring where every character appears at least k times.

For example:

Input: s = “aaabb”, k = 3
Output: 3
Valid substring: “aaa” (each character frequency ≥ 3)

Another example:

Input: s = “ababbc”, k = 2
Output: 5
Valid substring: “ababb” (both ‘a’ and ‘b’ appear at least 2 times)

---

Approach (Explained in Simple Language)

This is a divide-and-conquer string problem.
The key observation is:

If a character appears fewer than k times in the whole string,
that character can never be part of a valid answer.

So, that character acts like a boundary that splits the string into smaller parts.

For example:
String = “ababbc”, k = 2
Character ‘c’ appears only once.

So ‘c’ cannot be included.
We split:
“ababb” + ” ” + “”
Now solve separately on “ababb”.

---

Step-by-step Plan

1. Count frequency of every character in the current substring

If all characters appear at least k times, the whole substring is valid.

2. Find characters that appear less than k times

These characters “break” the string into smaller substrings because they cannot be part of the valid answer.

3. Split the string using these characters and recursively solve each part

Take the maximum answer from all parts.

4. Base Case

If the substring length is less than k, it can never qualify.

This divide-and-conquer approach gives excellent efficiency.

---

Java Code

public class LongestSubstringAtLeastKRepeating {

    public int longestSubstring(String s, int k) {
        return helper(s, 0, s.length(), k);
    }

    private int helper(String s, int start, int end, int k) {
        if (end - start < k) {
            return 0;
        }

        int[] freq = new int[26];
        for (int i = start; i < end; i++) {
            freq[s.charAt(i) - 'a']++;
        }

        for (int i = start; i < end; i++) {
            if (freq[s.charAt(i) - 'a'] < k) {
                int left = helper(s, start, i, k);
                int right = helper(s, i + 1, end, k);
                return Math.max(left, right);
            }
        }

        return end - start;
    }

    public static void main(String[] args) {
        LongestSubstringAtLeastKRepeating solution = new LongestSubstringAtLeastKRepeating();
        System.out.println(solution.longestSubstring("ababbc", 2));
    }
}

---

Dry Run

Performing a dry run on:

s = “ababbc”
k = 2

Step 1: initial call

helper(“ababbc”, 0, 6, 2)
Substring = “ababbc”

Count frequencies:
a = 2
b = 3
c = 1

Since c has frequency < 2, it cannot be in the valid substring.

We find c at index 5.
Split:

Left substring: “ababb” (index 0 to 4)
Right substring: “” (index 6 to 5 → empty)

Now solve each.

---

Step 2: Solve left substring

helper(“ababbc”, 0, 5, 2)
Substring = “ababb”

Frequencies:
a = 2
b = 3

All characters have frequency ≥ 2.

So the entire substring is valid.

Return length = 5 – 0 = 5.

---

Step 3: Solve right substring

helper(“”, 6, 6, 2)
Length is 0 < k, so return 0.

---

Step 4: Combine

Left result = 5
Right result = 0
Answer = max(5, 0) = 5

Final Output = 5

---

Why This Works Efficiently

The algorithm avoids scanning all substrings.
Instead, it splits only when it finds a weak character (frequency < k).
This drastically reduces unnecessary checks, making the solution fast even for long strings.

Time complexity is approximately O(26 × n) in practice because each split reduces the search area.