Longest Substring with At Least K Repeating Characters Python/Java solution

Python implementations commonly use the divide and conquer approach with recursion and a Counter or dictionary for frequency counting. Java solutions often implement the sliding window strategy using an integer array of size 26 for character frequencies. Both approaches achieve optimal or near-optimal time complexity depending on the method used.

What is the best approach for Longest Substring with At Least K Repeating Characters?

The most efficient approach uses a sliding window combined with iterating over the possible number of unique characters. For each unique character target (1–26), expand and shrink a window while tracking frequencies. This ensures every character in the window appears at least k times. The time complexity becomes O(26 * n), which is effectively O(n) for lowercase English letters.

Is Longest Substring with At Least K Repeating Characters asked at Google/Amazon/Meta?

This problem appears frequently in interviews at large tech companies because it tests string manipulation, frequency counting, and advanced sliding window logic. Variants of the problem have been reported in interviews at Amazon, Google, and Meta, especially for mid-level software engineering roles.

What data structure is used in Longest Substring with At Least K Repeating Characters?

The main data structure is a frequency counter implemented with an array or hash table. It tracks how many times each character appears in the current substring or segment. Combined with two pointers for sliding window or recursive splitting for divide and conquer, it enables efficient validation of the k-repetition condition.

What is the time complexity of Longest Substring with At Least K Repeating Characters?

The sliding window solution runs in O(26 * n) time because the algorithm scans the string once for each possible count of unique characters. Since the alphabet size is constant, this simplifies to O(n). The divide and conquer method typically runs in O(n log n) time due to recursive splits and repeated frequency counting.

Description Solution Video 21:05

395. Longest Substring with At Least K Repeating Characters

Q: Is Longest Substring with At Least K Repeating Characters easy or hard?

The problem is rated Medium because the constraint that every character must appear at least k times makes brute-force substring checks impractical. Recognizing that invalid characters split the string or that the sliding window must be constrained by unique counts requires deeper algorithmic insight.

Q: How to solve Longest Substring with At Least K Repeating Characters in O(n)?

Use a sliding window and iterate over the number of allowed unique characters. Maintain character frequency counts, a unique character counter, and a counter for characters meeting the k frequency requirement. Expand the window with the right pointer and shrink with the left pointer when constraints break. When both counters match, update the maximum substring length.

Medium46.8% acceptance10 companies

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.

Example 1:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input: s = "ababbc", k = 2
Output: 5
Explanation: The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Constraints:

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

Asked at 10 companies

Baidu Harness Tiktok Walmart Labs Amazon Microsoft

Google Yandex Meta Bloomberg

Topics

21:05

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

395. Longest Substring with At Least K Repeating Characters

Asked at 10 companies

Topics

Similar problems