Longest Substring with At Least K Repeating Characters

Longest Substring with At Least K Repeating Characters - Problem

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.

Note: A substring is a contiguous sequence of characters within a string.

Input & Output

Example 1 — Basic Case

$ Input: s = "aaabb", k = 3

› Output: 3

💡 Note: The longest substring is "aaa" where character 'a' appears 3 times, which meets the requirement k=3.

Example 2 — No Valid Substring

$ Input: s = "ababbc", k = 2

› Output: 5

💡 Note: The longest substring is "ababb" where 'a' appears 2 times and 'b' appears 3 times, both ≥ k=2.

Example 3 — Impossible Case

$ Input: s = "abc", k = 4

› Output: 0

💡 Note: No character appears 4 times since the string length is only 3, so return 0.

Constraints

1 ≤ s.length ≤ 10⁴
s consists of only lowercase English letters
1 ≤ k ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

String with character frequency requirement

Find Valid Substrings

Identify substrings where all chars appear ≥ k times

Return Length

Length of the longest valid substring

Key Takeaway

🎯 Key Insight: Characters that appear less than k times globally can never be part of a valid substring

Asked in

G Google 35 a Amazon 28 f Facebook 22 M Microsoft 18

The key insight is that if a character appears less than k times in the entire string, it cannot be part of any valid substring. The best approach uses divide and conquer to split at invalid characters or sliding window with fixed unique character counts. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force	O(n³)	O(1)	Check all possible substrings and count character frequencies
Sliding Window with Unique Character Count	O(n)	O(1)	Use sliding window for each possible number of unique characters
Divide and Conquer	O(n²)	O(n)	Split the string at characters that can't possibly be in valid substrings

Brute Force — Algorithm Steps

Generate all possible substrings
For each substring, count character frequencies
Check if all characters appear at least k times
Update maximum length if valid

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Substrings

Create all possible contiguous substrings

Count Frequencies

For each substring, count how often each character appears

Validate

Check if all characters meet the minimum frequency requirement

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(char* s, int k) {
    int n = strlen(s);
    int maxLength = 0;
    
    // Check all possible substrings
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            int len = j - i + 1;
            
            // Count character frequencies
            int charCount[26] = {0};
            for (int idx = i; idx <= j; idx++) {
                charCount[s[idx] - 'a']++;
            }
            
            // Check if all characters in substring appear at least k times
            int valid = 1;
            for (int idx = i; idx <= j; idx++) {
                if (charCount[s[idx] - 'a'] < k) {
                    valid = 0;
                    break;
                }
            }
            
            if (valid && len > maxLength) {
                maxLength = len;
            }
        }
    }
    
    return maxLength;
}

int main() {
    char s[1001];
    int k;
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    scanf("%d", &k);
    
    int result = solution(s, k);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops: O(n²) substrings × O(n) frequency counting per substring

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra space for frequency counting

✓ Linear Space

180.5K Views

Medium Frequency

~25 min Avg. Time

3.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler