Find longest substring with ≥k repeats
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
## Problem
You are given:
- a string `s` (consisting of lowercase English letters), and
- an integer `k`.
Return the length of the **longest contiguous substring** of `s` such that **every distinct character** in that substring appears **at least `k` times** within the substring.
If no such substring exists, return `0`.
## Input / Output
- **Input:** `s`, `k`
- **Output:** an integer length
## Constraints (typical interview bounds)
- `1 <= |s| <= 10^4`
- `1 <= k <= |s|`
- `s` contains only `'a'`–`'z'`
## Examples
1. `s = "aaabb"`, `k = 3` → output `3` (substring: `"aaa"`)
2. `s = "ababbc"`, `k = 2` → output `5` (substring: `"ababb"`)
3. `s = "abcd"`, `k = 2` → output `0`
Quick Answer: This question evaluates proficiency with string-processing techniques and character frequency analysis, focusing on algorithmic skills in the Coding & Algorithms domain. It is commonly asked to assess algorithmic reasoning about constraint handling, edge cases, and efficiency, and is positioned at the practical application level rather than purely conceptual understanding.
Return the length of the longest contiguous substring where every distinct character in that substring appears at least k times.
Constraints
- s contains lowercase English letters
- 1 <= k <= len(s) for normal cases
Examples
Input: ('aaabb', 3)
Expected Output: 3
Input: ('ababbc', 2)
Expected Output: 5
Input: ('abcd', 2)
Expected Output: 0
Input: ('weitong', 2)
Expected Output: 0
Input: ('abc', 1)
Expected Output: 3
Hints
- A character whose total frequency in a segment is below k cannot be inside a valid substring crossing that character.