What is the brute force approach and complexity for Longest Substring with At Least K Repeating Characters?

For each start, grow right and check all 26 counts after every step with time complexity O(26 · N²) and space complexity O(1).

What is the optimal approach and complexity for Longest Substring with At Least K Repeating Characters?

For u = 1..26, window with at most u distinct; valid when all u have ≥ k with optimal time complexity O(26 · N) and space complexity O(1).

Longest Substring with At Least K Repeating Characters

Q: How do you identify the pattern for Longest Substring with At Least K Repeating Characters?

Look for key signals in the prompt: "longest substring" indicates Looks like a variable window…; "every character appears at least k times" indicates …but "at least" on counts means a window can go from bad to good by growing. The rule is NOT monotonic.; "only lowercase letters" indicates At most 26 distinct letters → we can afford to fix the number of distinct letters and try all 26 values..

Medium·LeetCode #395 Pro OnlyTricky / Edge Case

LeetCode

Problem Statement

You are given a string s of lowercase letters and a number k.

Find the longest substring in which every letter that appears, appears at least k times. Return its length.

If no substring qualifies, return 0.

Input

A string s of lowercase English letters and an integer k.

Output

The length of the longest substring where each of its letters occurs at least k times, or 0.

Example 1

Input: s = "aaabb", k = 3

Output: 3

"aaa" works: 'a' appears 3 times. "aaabb" fails because 'b' appears only twice.

Example 2

Input: s = "ababbc", k = 2

Output: 5

"ababb" has 'a' twice and 'b' three times. Any substring with 'c' fails, because there is only one 'c'.

Constraints

• 1 ≤ s.length ≤ 10^4
• s contains only lowercase English letters
• 1 ≤ k ≤ 10^5

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“longest substring”

→ Looks like a variable window…

“every character appears at least k times”

→ …but "at least" on counts means a window can go from bad to good by growing. The rule is NOT monotonic.

“only lowercase letters”

→ At most 26 distinct letters → we can afford to fix the number of distinct letters and try all 26 values.

Approach Complexity Ladder

Brute Force — check every substringO(26 · N²)O(1)

For each start, grow right and check all 26 counts after every step

Better — divide and conquer on rare lettersO(26 · N)O(26)

Cut the string at letters that appear < k times, solve each piece

Optimal — fix the number of distinct letters, then slideO(26 · N)O(1)

For u = 1..26, window with at most u distinct; valid when all u have ≥ k

Brute Force Intuition

Try every start. Grow the end one letter at a time, keeping counts. After every step, check the 26 counts: each letter is either absent (0) or has at least k copies. If so, record the length. No early break: a substring that fails now may pass later, when more copies arrive.

Recognition rule for this sub-pattern:

Validity depends on the counts of things inside the window (distinct types, most frequent char, required letters). Keep a count map that updates on every add/remove.

Remember this · Sliding Window

Trigger

Contiguous subarray / substring + longest, shortest, maximum, count, or "of size K".

Think

Can I keep a valid range and move it, instead of checking every subarray from scratch?

Key question

When is my current window valid?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Sliding Window translate into production architectures and low-level memory mechanics.

LLD Machine Coding

Sliding Window Rate Limiter

Implementing token bucket and sliding log request throttlers in real backend services.

Explore Track

C++ Internals

Stack vs Heap, Placement new & Layout

Cache line locality when traversing contiguous windows in memory.

Explore Track

Minimum Window Substring