#395

Medium

auto_awesomeSliding window with running state updates

LeetCode Problem Workspace

Longest Substring with At Least K Repeating Characters

Find the length of the longest substring where every character appears at least k times using sliding window and divide-and-conquer patterns.

hash table string divide and conquer sliding window

Problem Statement

Given a string s and an integer k, identify the length of the longest contiguous substring where every character occurs at least k times. If no such substring exists, return 0. The input string consists only of lowercase English letters and can be up to 10,000 characters long.

For example, if s = "aaabb" and k = 3, the longest substring satisfying the condition is "aaa" with length 3. If s = "ababbc" and k = 2, the answer is 5 for substring "ababb". Your solution should efficiently handle large strings using appropriate data structures and algorithms tied to character frequency tracking.

Examples

Example 1

Input: s = "aaabb", k = 3

Output: 3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2

Input: s = "ababbc", k = 2

Output: 5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Constraints

1 <= s.length <= 104
s consists of only lowercase English letters.
1 <= k <= 105

Solution Approach

Frequency Map and Split Points

Compute the frequency of each character. Characters appearing fewer than k times cannot be in any valid substring. Use them as split points to divide the string and recursively solve for each segment, ensuring every character in a substring meets the threshold.

Sliding Window with Dynamic Counters

Use a sliding window to track counts of characters in the current substring segment. Expand the window until an invalid character violates the k condition, then shrink or split at that point. Update the maximum length whenever a valid window is found.

Combine Divide and Conquer with Window Tracking

Merge both strategies by recursively splitting at invalid characters while also applying a sliding window inside segments. This allows handling complex distributions efficiently and avoids repeated scanning of invalid portions, optimizing both time and space usage.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	\mathcal{O}(1)

Time complexity is O(n) on average with recursive splits depending on character distribution. Space complexity is O(1) for counters if using fixed-size arrays for lowercase letters.

What Interviewers Usually Probe

Check if the candidate identifies characters below k as natural split points.
Listen for mention of recursive divide-and-conquer or sliding window with frequency counters.
Evaluate awareness of worst-case behavior when many characters fall below k.

Common Pitfalls or Variants

Common pitfalls

Counting frequencies globally without handling splits leads to incorrect substring lengths.
Not updating window counters dynamically can cause unnecessary rescanning.
Failing to handle edge cases where no valid substring exists, returning negative or wrong values.

Follow-up variants

Find the longest substring with at least k occurrences of exactly m distinct characters.
Determine the number of substrings where each character occurs at least k times.
Compute the longest substring allowing at most x characters to appear fewer than k times.

FAQ

What is the key strategy for Longest Substring with At Least K Repeating Characters?

The core strategy is using character frequency to split the string at invalid points, combined with sliding window updates to track valid substrings efficiently.

Can a sliding window alone solve this problem?

A sliding window alone may not capture all valid segments if characters below k are present, so combining it with divide-and-conquer ensures correctness.

What is the time complexity for this problem?

Time complexity is roughly O(n) on average, but depends on how many splits occur due to characters below the k threshold.

What data structures are most useful here?

Fixed-size arrays or hash maps for character counts are ideal, enabling quick frequency checks and efficient window updates.

How do I handle strings with no valid substring?

If no character meets the minimum repetition k, return 0 immediately to avoid unnecessary computation.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        def dfs(l, r):
            cnt = Counter(s[l : r + 1])
            split = next((c for c, v in cnt.items() if v < k), '')
            if not split:
                return r - l + 1
            i = l
            ans = 0
            while i <= r:
                while i <= r and s[i] == split:
                    i += 1
                if i >= r:
                    break
                j = i
                while j <= r and s[j] != split:
                    j += 1
                t = dfs(i, j - 1)
                ans = max(ans, t)
                i = j
            return ans

        return dfs(0, len(s) - 1)

Continue Practicing

#424 longest repeating character replacement #438 find all anagrams in a string #567 permutation in string