How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at TikTok during technical interviews.

Find substring where all chars appear at least k

Company: TikTok

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

You are given a string s and an integer k (1 ≤ k ≤ |s|). Return the length of the longest substring in which every distinct character occurs at least k times. If no such substring exists, return 0. Describe your algorithm, explain why it is correct, and analyze its time and space complexity. Discuss edge cases such as k = 1, k > |s|, and strings with all unique characters.

Quick Answer: This question evaluates proficiency in string processing, frequency analysis, and algorithmic reasoning for constrained-substring problems, along with the ability to analyze time and space complexity.

You are given a string `s` and an integer `k` (1 ≤ k ≤ |s|). Return the length of the longest substring of `s` in which every distinct character occurs at least `k` times. If no such substring exists, return 0. A valid substring is a contiguous slice of `s`; within that slice, each character that appears must appear at least `k` times. You want the longest such slice. **Examples** - `s = "aaabb", k = 3` → `3`. The substring `"aaa"` has every character (`a`) appearing 3 ≥ 3 times; `"aaabb"` fails because `b` appears only twice. - `s = "ababbc", k = 2` → `5`. The substring `"ababb"` has `a` appearing 2 times and `b` appearing 3 times, both ≥ 2. **Edge cases to consider** - `k = 1`: every character trivially appears at least once, so the answer is `len(s)`. - `k > |s|`: no substring can have any character appear `k` times, so the answer is 0. - All-unique characters with `k > 1`: no character repeats, so the answer is 0.

Constraints

1 <= len(s) (the string is non-empty in typical inputs; an empty string returns 0)
1 <= k <= len(s) per the prompt, though the solution also handles k > len(s) by returning 0
s consists of lowercase (or general) characters
Return 0 when no valid substring exists

Examples

Input: ("aaabb", 3)

Expected Output: 3

Explanation: "aaa" is the longest substring where every char (a) appears >= 3 times. "aaabb" fails because b appears only twice.

Input: ("ababbc", 2)

Expected Output: 5

Explanation: "ababb" has a appearing 2 times and b appearing 3 times, both >= 2. Adding c (count 1) would break it.

Input: ("", 1)

Expected Output: 0

Explanation: Empty string has no substring, so the answer is 0.

Input: ("abcde", 2)

Expected Output: 0

Explanation: All characters are unique; no character appears twice, so no valid substring exists with k=2.

Input: ("aaa", 5)

Expected Output: 0

Explanation: k=5 exceeds the string length; a appears only 3 times, so no valid substring exists.

Input: ("a", 1)

Expected Output: 1

Explanation: With k=1 every character trivially qualifies, so the whole string is valid.

Input: ("bbaaacbd", 3)

Expected Output: 3

Explanation: "aaa" is the longest valid substring; b and c never reach 3 in any window that also keeps a's together.

Input: ("aabbcc", 2)

Expected Output: 6

Explanation: Each of a, b, c appears exactly 2 times across the whole string, so the entire string is valid with k=2.

Hints

If a character appears fewer than k times in the whole string, it can never be part of any valid substring — so any valid substring must lie entirely between occurrences of that character. This naturally suggests a divide-and-conquer split.
Count the frequency of each character. Pick a character whose total count is less than k and split the string on every occurrence of it; recurse on each resulting fragment and take the maximum.
Base cases: if k <= 1, the answer is len(s); if every character in the current fragment already appears at least k times, that whole fragment is valid and its length is the answer.
An alternative O(N) sliding-window approach fixes the number of distinct characters t (1..26) allowed in the window and slides a window keeping exactly t distinct chars, checking that each appears >= k times.

Quick Overview

This question evaluates proficiency in string processing, frequency analysis, and algorithmic reasoning for constrained-substring problems, along with the ability to analyze time and space complexity.