algo-string-01

# 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).

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

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.

To solve this problem, we need to find the length of the longest substring of a given string `s` that occurs at least `k` times. If no such substring exists, we return 0.

### Approach
The approach involves using a combination of binary search and rolling hash (Rabin-Karp algorithm) to efficiently determine the longest substring that meets the criteria. Here's a detailed breakdown of the approach:

1. **Edge Cases Handling**: 
   - If the string `s` is empty, return 0.
   - If `k` is 1, return the length of `s` since every non-empty substring of `s` occurs at least once.

2. **Precomputation**:
   - Compute prefix hashes and power arrays for two different bases and moduli to minimize collision probability. This helps in efficiently computing the hash of any substring in constant time.

3. **Binary Search**:
   - Use binary search to determine the maximum length `L` of the substring that occurs at least `k` times. The search range is from 1 to the length of `s`.

4. **Rolling Hash Check**:
   - For each midpoint length `L` during the binary search, use the precomputed hashes to check if any substring of length `L` occurs at least `k` times. This is done using a helper function that counts the frequency of each substring's hash.

### Solution Code
```python
def longest_k_repeated(s: str, k: int) -> int:
    if not s:
        return 0
    if k == 1:
        return len(s)
    
    base1 = 911382629
    mod1 = 10**18 + 3
    base2 = 3571428571
    mod2 = 10**18 + 7
    
    n = len(s)
    H1 = [0] * (n + 1)
    H2 = [0] * (n + 1)
    power1 = [1] * (n + 1)
    power2 = [1] * (n + 1)
    
    for i in range(n):
        H1[i+1] = (H1[i] * base1 + ord(s[i])) % mod1
        H2[i+1] = (H2[i] * base2 + ord(s[i])) % mod2
        power1[i+1] = (power1[i] * base1) % mod1
        power2[i+1] = (power2[i] * base2) % mod2
    
    def has_substring(L):
        if L == 0:
            return False
        count = {}
        for i in range(n - L + 1):
            h1 = (H1[i+L] - H1[i] * power1[L]) % mod1
            h2 = (H2[i+L] - H2[i] * power2[L]) % mod2
            key = (h1, h2)
            if key in count:
                count[key] += 1
                if count[key] >= k:
                    return True
            else:
                count[key] = 1
        return False
    
    low = 1
    high = n
    answer = 0
    
    while low <= high:
        mid = (low + high) // 2
        if has_substring(mid):
            answer = mid
            low = mid + 1
        else:
            high = mid - 1
    
    return answer
```

### Explanation
1. **Precomputation**: We precompute the prefix hashes and power arrays for two different bases and moduli. This allows us to compute the hash of any substring in constant time using the rolling hash technique.

2. **Binary Search**: We perform a binary search on the possible lengths of the substring. For each midpoint length, we check if any substring of that length occurs at least `k` times using the helper function.

3. **Helper Function**: The helper function uses the precomputed hashes to efficiently count the occurrences of each substring of a given length. By using two different hash functions, we minimize the probability of hash collisions, ensuring accurate results.

This approach ensures that we efficiently find the longest substring that meets the criteria in O(n log n) time, making it suitable for large input sizes.

Okay, I need to solve this problem where I have to find the longest substring that occurs at least k times in the given string s. Hmm, let's think about how to approach this.

First, let's understand the problem. For a given string s and integer k, I have to return the maximum length L such that there's a substring of length L that appears at least k times. If no such substring exists, return 0.

Let's look at the examples to get a better idea. For instance, in "banana" with k=2, the answer is 3 because "ana" appears at positions 1 and 3. Oh right, and overlaps are allowed, so "aaa" with k=2 would have "aa" appearing at 0 and 1.

So, the naive approach would be to check all possible substrings, count their occurrences, and find the maximum length that meets the condition. But that's O(n^2), which is too slow for large strings (like 1e5 characters). So I need a more efficient method.

What's a better way? I remember that suffix arrays and suffix automata can be used for substring problems. Suffix automata are efficient for such tasks because they can represent all substrings in linear space and allow for quick queries.

Wait, another approach is binary search on the possible lengths. For each possible length L, check if there exists a substring of length L that occurs at least k times. The maximum possible L is the length of the string, and the minimum is 1. So, binary search can help reduce the number of checks.

But how do I efficiently check for a given L whether any substring of that length appears at least k times?

Hmm, for each L, I can compute the frequency of each substring of length L and see if any frequency is >=k. But computing this for each L in binary search would be O(n) per check, leading to O(n log n) time overall, which is acceptable for n=1e5.

Wait, but for each L, how do I compute the frequencies efficiently? Using a sliding window and a hash map. For example, for L=3, slide a window of 3 characters across the string, count how many times each substring appears. If any count is >=k, then L is possible.

But for each L, this is O(n) time. Since binary search would have log n steps, the total time is O(n log n), which is acceptable.

So the plan is:

1. Handle edge cases first. Like when k=1, return len(s) if s is non-empty. Or when s is empty, return 0.

2. For other cases, perform a binary search on possible L values. The lower bound is 1, upper bound is len(s).

3. For each mid value in binary search, check if any substring of length mid occurs at least k times.

4. If such a substring exists, try to find a longer L by adjusting the binary search. Otherwise, try shorter.

Now, the key is implementing the check efficiently.

Wait, but for each mid, how do I check quickly? For each mid, I can use a sliding window and a hash (like a dictionary) to count the occurrences. But for mid up to 1e5, and n up to 1e5, each check is O(n), which is manageable.

But wait, for each binary step, it's O(n). So for log n steps, it's O(n log n), which is acceptable for n=1e5.

So the steps are:

- Binary search between low=1 and high=len(s).

- For mid = (low + high) // 2, check if any substring of length mid appears at least k times.

- If yes, set low = mid + 1, else set high = mid -1.

Wait, no. Wait, the binary search needs to find the maximum L where the condition is true. So the initial low is 1, high is len(s). We want the largest L where the condition holds.

So during each step, if for mid, the condition is true, we can try to see if a larger L exists. So set low = mid + 1. Else, set high = mid -1.

Wait, but the binary search needs to find the maximum L where the condition is true. So the standard approach is to adjust the search accordingly.

Wait, perhaps the binary search can be structured as follows:

Initialize low = 1, high = len(s), answer = 0.

While low <= high:

   mid = (low + high) // 2

   if any substring of length mid occurs at least k times:

       answer = mid

       low = mid + 1

   else:

       high = mid -1

At the end, return answer.

Yes, that makes sense.

So the main part is implementing the check for a given L.

Now, how to implement the check efficiently.

For a given L, we can slide a window of size L across the string, and for each window, record the substring in a dictionary, counting how many times each substring occurs.

If any substring's count reaches k, we can immediately return True for this L.

But for L=1e5, the window is the entire string, so the check is O(1). For L=5e4, it's O(2) steps, etc. So for each L, the check is O(n) time.

But for n=1e5, and log n steps, the total time is O(n log n), which is acceptable.

Wait, but for each L, the number of substrings is O(n), and each step is O(1) for the hash. So yes, O(n) per check.

So the plan is feasible.

Now, let's think about the code.

First, handle the edge cases:

- If s is empty, return 0.

- If k == 1, return len(s) if s is not empty.

Else, proceed with binary search.

Wait, but what if k is 1 and s is non-empty? Then the entire string occurs once, so return len(s). So that's an edge case.

So in code:

if not s:
    return 0
if k == 1:
    return len(s)

Else, proceed.

Now, for the binary search.

Implement a helper function that, given L, returns True if any substring of length L occurs at least k times.

Implement this helper function.

So, in code:

def has_substring(s, L, k):
    count = {}
    for i in range(len(s) - L + 1):
        substr = s[i:i+L]
        if substr in count:
            count[substr] += 1
            if count[substr] >= k:
                return True
        else:
            count[substr] = 1
    return False

Wait, but for L=0, but L starts from 1, so no problem.

But for L= len(s), it's only one substring.

But for L larger than len(s), it's invalid, but in the binary search, high is len(s), so mid can't be larger than that.

So the helper function is correct.

But wait, for each L, the helper function is O(n) time, which is acceptable.

But for L=1e5, the helper function will process only one substring, which is O(1) time.

So the code is manageable.

Now, let's test this approach with 
…[15882 chars elided]…
f L == 0:
            return False
        count = {}
        for i in range(n - L + 1):
            h1 = (H1[i+L] - H1[i] * power1[L]) % mod1
            h2 = (H2[i+L] - H2[i] * power2[L]) % mod2
            key = (h1, h2)
            if key in count:
                count[key] += 1
                if count[key] >= k:
                    return True
            else:
                count[key] = 1
        return False
    
    low = 1
    high = n
    answer = 0
    
    while low <= high:
        mid = (low + high) // 2
        if has_substring(mid):
            answer = mid
            low = mid + 1
        else:
            high = mid -1
    
    return answer

Yes, this should work.

Now, let's test this code with the examples.

Test case 1: s = "banana", k=2.

The code should return 3.

Test case 2: s = "banana", k=3 → returns 1.

Test case 3: s = "aaa", k=2 → returns 2.

Test case 4: s = "abcdef", k=2 → returns 0.

All should pass.

Another test case: s = "aaaa", k=2 → the substrings of length 3 are "aaa" at positions 0 and 1. So the helper function for L=3 would return True. So the code would find L=3 as the maximum.

But wait, in "aaaa", the maximum L is 3, which occurs twice.

Yes.

Another test case: s = "aaaaa", k=3.

Substrings of length 3: "aaa" occurs at 0,1,2 → count 3. So the helper function for L=3 returns True. So the code would return 3.

Yes.

Now, what about when k is larger than the maximum possible?

Like s = "abc", k=4 → returns 0.

Yes.

Now, the code seems correct.

But what about when the string is very long, like 1e5 characters, and k is 1.

The code correctly returns len(s).

Another test case: s = "ababab", k=3.

Substrings of length 2: "ab" occurs 3 times. So the code should return 2.

Yes.

So, the code should handle all cases correctly.

Now, the only thing left is to implement this in Python.

But wait, what about the precomputation of H and power?

Yes, the code correctly precomputes H1, H2, power1, power2.

Now, the code is as written above.

So, the final code is as follows.