algo-string-01
1.000
Challenge · difficulty 4/5
# Longest k-repeated substring
Implement a file **`solution.py`** containing a function `longest_k_repeated`:
```python
def longest_k_repeated(s: str, k: int) -> int:
"""Return the length of the longest substring of `s` that occurs
at least `k` times."""
```
Given a string `s` and an integer `k >= 1`, return the **length of the longest
non-empty substring** of `s` that occurs **at least `k` times** in `s`. If no
non-empty substring occurs at least `k` times, return `0`.
## What counts as an occurrence
- An occurrence is a **distinct starting position** in `s`. A substring of
length `L` occurs at position `i` iff `s[i:i+L]` equals it.
- **Overlaps are allowed.** For example, in `"aaaa"` the substring `"aaa"`
occurs at positions `0` and `1`, so it occurs **2** times.
- The string is compared **exactly**, character by character; matching is
**case-sensitive** and works over arbitrary Unicode characters.
## Precise definition
Return the largest `L >= 1` such that there exists a string `w` of length `L`
for which the number of indices `i` with `s[i:i+L] == w` is `>= k`. If no such
`L` exists, return `0`.
## Edge cases
- `k == 1`: every non-empty substring occurs at least once, so for a non-empty
`s` the answer is `len(s)` (the whole string occurs once). For the empty
string the answer is `0`.
- The empty string returns `0` for **every** `k`.
- If `k` exceeds the length of the longest single-character run and the string
has no repeats at all (e.g. all-distinct characters), smaller substrings may
still fail the threshold — return `0` when nothing qualifies.
## Worked examples
```python
assert longest_k_repeated("banana", 2) == 3 # "ana" occurs at 1 and 3 (overlap)
assert longest_k_repeated("banana", 3) == 1 # only single chars occur >= 3 times
assert longest_k_repeated("banana", 4) == 0
assert longest_k_repeated("aaa", 2) == 2 # "aa" at 0 and 1
assert longest_k_repeated("aaa", 3) == 1 # "a" x3
assert longest_k_repeated("abcabc", 1) == 6 # whole string, k==1
assert longest_k_repeated("abcdef", 2) == 0 # all distinct, nothing repeats
assert longest_k_repeated("", 5) == 0
```
## Efficiency
Inputs can be **large**: `len(s)` up to about `100000`. A naive approach that
enumerates every substring is `O(n^2)` in time and memory and will time out.
Aim for roughly `O(n)` or `O(n log n)`. (A suffix automaton, or a suffix array
with LCP, or binary-search-plus-hashing all work.)
## Constraints
- `1 <= k`
- `0 <= len(s) <= 100000`
- `s` consists of arbitrary characters (tests use printable ASCII).tests/test_longest_k_repeated.py
import random
from solution import longest_k_repeated
def brute(s, k):
"""O(n^2) reference oracle for small strings."""
n = len(s)
if n == 0 or k < 1:
return 0
for L in range(n, 0, -1):
seen = {}
for i in range(n - L + 1):
sub = s[i:i + L]
c = seen.get(sub, 0) + 1
seen[sub] = c
if c >= k:
return L
return 0
def test_empty_string():
assert longest_k_repeated("", 1) == 0
assert longest_k_repeated("", 2) == 0
assert longest_k_repeated("", 5) == 0
def test_k_one_is_whole_string():
assert longest_k_repeated("a", 1) == 1
assert longest_k_repeated("abc", 1) == 3
assert longest_k_repeated("abcabc", 1) == 6
def test_no_repeat_returns_zero():
# All distinct characters: nothing occurs twice.
assert longest_k_repeated("abcdef", 2) == 0
assert longest_k_repeated("a", 2) == 0
assert longest_k_repeated("xyz", 3) == 0
def test_single_char_runs():
# "aaa": 'a' x3, 'aa' x2, 'aaa' x1
assert longest_k_repeated("aaa", 1) == 3
assert longest_k_repeated("aaa", 2) == 2
assert longest_k_repeated("aaa", 3) == 1
assert longest_k_repeated("aaa", 4) == 0
def test_banana():
# classic: "ana" occurs at positions 1 and 3 (overlapping)
assert longest_k_repeated("banana", 2) == 3
# "a" occurs 3 times, "an"/"na" twice, "ana" twice
assert longest_k_repeated("banana", 3) == 1
assert longest_k_repeated("banana", 4) == 0
def test_overlapping_counts():
# "aaaa": "aaa" occurs at 0 and 1 -> length 3 for k=2
assert longest_k_repeated("aaaa", 2) == 3
assert longest_k_repeated("aaaa", 3) == 2
assert longest_k_repeated("aaaa", 4) == 1
def test_disjoint_repeat():
# "abcXabc": "abc" occurs twice, no overlap
assert longest_k_repeated("abcXabc", 2) == 3
assert longest_k_repeated("abcXabc", 3) == 0
def test_mixed_case_sensitive():
# 'A' and 'a' are different characters.
# "AaAa": "Aa" occurs at 0 and 2 (len 2); "AaA" occurs once, "aAa" once.
assert longest_k_repeated("AaAa", 2) == 2
def test_period_two_medium():
s = "ab" * 50
n = len(s)
# periodic with period 2: s[0..n-3] == s[2..n-1]
assert longest_k_repeated(s, 2) == n - 2
def test_matches_brute_small_random():
rng = random.Random(1234)
for _ in range(400):
n = rng.randint(0, 12)
alpha = "ab" if rng.random() < 0.5 else "abc"
s = "".join(rng.choice(alpha) for _ in range(n))
for k in range(1, 6):
assert longest_k_repeated(s, k) == brute(s, k), (s, k)
def test_matches_brute_larger_alphabet():
rng = random.Random(99)
for _ in range(150):
n = rng.randint(0, 40)
s = "".join(rng.choice("abcde") for _ in range(n))
for k in range(1, 4):
assert longest_k_repeated(s, k) == brute(s, k), (s, k)
def test_large_all_same():
s = "a" * 100000
assert longest_k_repeated(s, 2) == 99999
assert longest_k_repeated(s, 100000) == 1
assert longest_k_repeated(s, 100001) == 0
def test_large_period_two():
s = "ab" * 50000
n = len(s) # 100000
assert longest_k_repeated(s, 2) == n - 2
def test_large_no_long_repeat():
# Random over a 10-char alphabet: the longest repeat must be short.
rng = random.Random(7)
s = "".join(rng.choice("abcdefghij") for _ in range(60000))
ans = longest_k_repeated(s, 2)
# There must be some repeat (pigeonhole on length-1 substrings), and it
# should be far shorter than the whole string.
assert 1 <= ans < 1000
System prompt
You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.Proposed solution
```python
def longest_k_repeated(s: str, k: int) -> int:
"""Return the length of the longest substring of `s` that occurs
at least `k` times."""
n = len(s)
if n == 0 or k > n:
return 0
if k == 1:
return n
# Precompute character codes for faster access
ords = [ord(c) for c in s]
# Double hashing parameters to minimize collision probability
MOD1 = 10**9 + 7
BASE1 = 313
MOD2 = 10**9 + 9
BASE2 = 317
def check(length: int) -> bool:
"""Check if any substring of given length occurs at least k times."""
h1 = h2 = 0
pow1 = pow(BASE1, length, MOD1)
pow2 = pow(BASE2, length, MOD2)
counts = {}
for i in range(n):
c = ords[i]
h1 = (h1 * BASE1 + c) % MOD1
h2 = (h2 * BASE2 + c) % MOD2
if i >= length:
prev = ords[i - length]
h1 = (h1 - prev * pow1) % MOD1
h2 = (h2 - prev * pow2) % MOD2
if i >= length - 1:
key = (h1, h2)
cnt = counts.get(key, 0) + 1
counts[key] = cnt
if cnt >= k:
return True
return False
low, high = 1, n
ans = 0
while low <= high:
mid = (low + high) // 2
if check(mid):
ans = mid
low = mid + 1
else:
high = mid - 1
return ans
```Test output (stdout)
.............. [100%]
14 passed in 0.78s
Reasoning (chain-of-thought)
The problem asks for the length of the longest substring of a given string `s` that occurs at least `k` times.
Constraints: `len(s)` up to 100,000. `k >= 1`.
We need an efficient solution, ideally $O(n)$ or $O(n \log n)$.
Let's consider possible approaches:
1. Binary search on the length `L` + rolling hash (Rabin-Karp) to check if any substring of length `L` occurs at least `k` times.
- Checking for a fixed `L`: compute rolling hashes for all substrings of length `L`, count frequencies using a hash map. If any count >= `k`, return True.
- Time complexity: $O(n \log n)$ because binary search takes $O(\log n)$ steps, and each step takes $O(n)$ time.
- Space complexity: $O(n)$ for the hash map.
- Collisions might be an issue, but with a large modulus or double hashing, it's very unlikely. Given it's a programming problem, usually single large modulus or Python's arbitrary precision integers (though slower) or just standard hashing is fine. Actually, Python's `hash()` is not stable across runs, but we can implement our own rolling hash. Or we can just use Python's built-in string slicing and dictionary, but slicing takes $O(L)$, making the check $O(nL)$, which is too slow. Rolling hash is better.
- Wait, Python's `dict` with string keys actually computes hash of the string, which takes $O(L)$. So checking all substrings of length `L` with a dict would be $O(nL)$. With binary search, worst case $O(n^2)$. So rolling hash is necessary.
- Alternatively, we can use a Suffix Automaton or Suffix Array. Suffix Automaton construction is $O(n)$ and can directly give the answer. Each state in the SAM represents a set of substrings. For each state, we can compute the number of occurrences of the substrings it represents. The maximum length in a state with occurrence count >= `k` is a candidate answer.
- Suffix Array + LCP array construction is $O(n \log n)$ or $O(n)$. With LCP array, we can find the longest substring occurring at least `k` times by looking at windows of size `k-1` in the LCP array. The minimum LCP in a window of size `k-1` gives the length of the longest common prefix among `k` suffixes. The maximum of these minimums over all windows is the answer. This is a standard technique and very robust.
- Let's verify the Suffix Array + LCP approach:
- Construct SA and LCP arrays.
- If `k == 1`, answer is `len(s)`.
- If `k > len(s)`, answer is 0.
- Otherwise, iterate `i` from 0 to `n - k`. The window of suffixes starting at `SA[i], SA[i+1], ..., SA[i+k-1]` share a common prefix of length `min(LCP[i+1], ..., LCP[i+k-1])`. (Note: LCP array usually has size `n`, where `LCP[i]` is the length of the longest common prefix between suffix `SA[i-1]` and `SA[i]`. So for a window of `k` suffixes from index `i` to `i+k-1` in SA, the relevant LCP values are `LCP[i+1]` to `LCP[i+k-1]`. There are `k-1` such values.)
- We need the maximum over all `i` of `min(LCP[i+1 : i+k])`.
- This can be computed in $O(n)$ using a sliding window minimum algorithm (deque) or simply in $O(nk)$ if $k$ is small, but $k$ can be large. Sliding window minimum is $O(n)$.
- Constructing SA and LCP in Python efficiently might be tricky without external libraries, but we can implement a simple $O(n \log^2 n)$ or $O(n \log n)$ SA construction, or use the built-in sorting with a trick. Actually, Python's `sorted` with key can construct SA in $O(n^2 \log n)$ worst case, but for random strings it's faster. However, for competitive programming, we usually implement a proper SA construction or use the rolling hash binary search which is easier to implement and less error-prone in Python.
- Let's stick to Binary Search + Rolling Hash. It's simpler to implement correctly in a short time.
- Rolling hash details:
- Base $B = 131$ or $257$ or larger. Modulo $M = 10^9 + 7$ or $2^{61}-1$.
- Precompute powers of $B$.
- For a given length `L`, compute hash of `s[0:L]`. Then slide: `h = (h * B + ord(s[i]) - ord(s[i-L]) * powB[L]) % M`.
- Use a dictionary to count frequencies. If any count reaches `k`, return True.
- To avoid collisions, we can use double hashing or just rely on Python's large integers (no modulo) but that might be slow. Actually, Python handles large ints automatically, but hashing large ints is slower. Using a large prime modulo like $2^{61}-1$ is safe and fast.
- Wait, collisions are possible but extremely unlikely with $M \approx 10^{18}$ or double hash. Given constraints and typical test cases, a single large modulus or double hash is fine. I'll use double hash to be safe, or just one large modulus $2^{61}-1$.
- Actually, Python's `hash()` on strings is randomized per process, but we can't rely on it for rolling.
- Let's implement a robust rolling hash with modulus $M = 2^{61} - 1$ (Mersenne prime) and base $B = 131$.
- Or even simpler: since we just need to pass tests, maybe binary search + dictionary of substrings is acceptable if we optimize? No, slicing is $O(L)$, total $O(n^2)$.
- I'll implement binary search + rolling hash.
Let's refine the rolling hash check function:
```python
def check(length, s, k):
if length == 0: return True
n = len(s)
if length > n: return False
MOD = 2**61 - 1
BASE = 131
pow_base = pow(BASE, length, MOD)
h = 0
counts = {}
for i in range(n):
h = (h * BASE + ord(s[i])) % MOD
if i >= length:
h = (h - ord(s[i-length]) * pow_base) % MOD
if i >= length - 1:
counts[h] = counts.get(h, 0) + 1
if counts[h] >= k:
return True
return False
```
Wait, collisions could cause false positives. To be strictly correct, we might need to verify collisions or use double hashing. Given it's a coding problem, usually single hash with large modulus is accepted, but to be safe, I'll use double hashing or just verify on collision. Actually, verifying on collision is easy: store list of indices for each hash, a
…[14357 chars elided]…
hon
def longest_k_repeated(s: str, k: int) -> int:
n = len(s)
if n == 0 or k > n:
return 0
if k == 1:
return n
ords = [ord(c) for c in s]
MOD1 = 10**9 + 7
BASE1 = 313
MOD2 = 10**9 + 9
BASE2 = 317
def check(length):
h1 = h2 = 0
pow1 = pow(BASE1, length, MOD1)
pow2 = pow(BASE2, length, MOD2)
counts = {}
for i in range(n):
c = ords[i]
h1 = (h1 * BASE1 + c) % MOD1
h2 = (h2 * BASE2 + c) % MOD2
if i >= length:
prev = ords[i-length]
h1 = (h1 - prev * pow1) % MOD1
h2 = (h2 - prev * pow2) % MOD2
if i >= length - 1:
key = (h1, h2)
cnt = counts.get(key, 0) + 1
counts[key] = cnt
if cnt >= k:
return True
return False
low, high = 1, n
ans = 0
while low <= high:
mid = (low + high) // 2
if check(mid):
ans = mid
low = mid + 1
else:
high = mid - 1
return ans
```
This matches all requirements. I'll output it.
One minor point: `counts.get(key, 0)` might be slightly slower than `defaultdict`, but it's fine. I'll keep it as is for zero dependencies.
All good.
Output matches.
Proceeds.
[Final Check]
- Function signature matches.
- Handles edge cases.
- Efficient $O(n \log n)$.
- Correct logic.
- Ready.
Output generation.
*(Self-Correction/Refinement during generation prep)*:
I realize that `h1 = (h1 - prev * pow1) % MOD1` works, but in Python, negative modulo results in positive, which is correct.
The code is solid.
I will present it now.
[Output Generation] -> *Proceeds*