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.

```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."""
    if k > len(s) or k <= 0:
        return 0

    n = len(s)
    if n == 0:
        return 0

    # Suffix array and LCP
    suffix_array = build_suffix_array(s)
    lcp = build_lcp(s, suffix_array)

    # Binary search for the longest substring
    left, right = 0, n
    while left < right:
        mid = (left + right + 1) // 2
        if has_repeated_substring(s, mid, k):
            left = mid
        else:
            right = mid - 1

    return left

def build_suffix_array(s: str) -> list:
    # Implement suffix array construction
    pass

def build_lcp(s: str, suffix_array: list) -> list:
    # Implement LCP array construction
    pass

def has_repeated_substring(s: str, length: int, k: int) -> bool:
    # Check if there is a substring of given length that occurs at least k times
    pass
```

[
  {
    "total": 14,
    "answer": "```python\ndef longest_k_repeated(s: str, k: int) -> int:\n    \"\"\"Return the length of the longest substring of `s` that occurs\n    at least `k` times.\"\"\"\n    if k > len(s) or k <= 0:\n        return 0\n\n    n = len(s)\n    if n == 0:\n        return 0\n\n    # Suffix array and LCP\n    suffix_array = build_suffix_array(s)\n    lcp = build_lcp(s, suffix_array)\n\n    # Binary search for the longest substring\n    left, right = 0, n\n    while left < right:\n        mid = (left + right + 1) // 2\n        if has_repeated_substring(s, mid, k):\n            left = mid\n        else:\n            right = mid - 1\n\n    return left\n\ndef build_suffix_array(s: str) -> list:\n    # Implement suffix array construction\n    pass\n\ndef build_lcp(s: str, suffix_array: list) -> list:\n    # Implement LCP array construction\n    pass\n\ndef has_repeated_substring(s: str, length: int, k: int) -> bool:\n    # Check if there is a substring of given length that occurs at least k times\n    pass\n```",
    "passed": 2,
    "test_error": "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', 2)\n\ntest_longest_k_repeated.py:104: AssertionError\n____________________________ test_large_period_two _____________________________\n\n    def test_large_period_two():\n        s = \"ab\" * 50000\n        n = len(s)  # 100000\n>       assert longest_k_repeated(s, 2) == n - 2\nE       AssertionError: assert 0 == (100000 - 2)\nE        +  where 0 = longest_k_repeated('ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababa...ababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab', 2)\n\ntest_longest_k_repeated.py:112: AssertionError\n__________________________ test_large_no_long_repeat ___________________________\n\n    def test_large_no_long_repeat():\n        # Random over a 10-char alphabet: the longest repeat must be short.\n        rng = random.Random(7)\n        s = \"\".join(rng.choice(\"abcdefghij\") for _ in range(60000))\n        ans = longest_k_repeated(s, 2)\n        # There must be some repeat (pigeonhole on length-1 substrings), and it\n        # should be far shorter than the whole string.\n>       assert 1 <= ans < 1000\nE       assert 1 <= 0\n\ntest_longest_k_repeated.py:122: AssertionError\n=========================== short test summary info ============================\nFAILED test_longest_k_repeated.py::test_k_one_is_whole_string - AssertionErro...\nFAILED test_longest_k_repeated.py::test_single_char_runs - AssertionError: as...\nFAILED test_longest_k_repeated.py::test_banana - AssertionError: assert 0 == 3\nFAILED test_longest_k_repeated.py::test_overlapping_counts - AssertionError: ...\nFAILED test_longest_k_repeated.py::test_disjoint_repeat - AssertionError: ass...\nFAILED test_longest_k_repeated.py::test_mixed_case_sensitive - AssertionError...\nFAILED test_longest_k_repeated.py::test_period_two_medium - AssertionError: a...\nFAILED test_longest_k_repeated.py::test_matches_brute_small_random - Assertio...\nFAILED test_longest_k_repeated.py::test_matches_brute_larger_alphabet - Asser...\nFAILED test_longest_k_repeated.py::test_large_all_same - AssertionError: asse...\nFAILED test_longest_k_repeated.py::test_large_period_two - AssertionError: as...\nFAILED test_longest_k_repeated.py::test_large_no_long_repeat - assert 1 <= 0\n12 failed, 2 passed in 0.04s"
  },
  {
    "total": 1,
    "answer": "```python\ndef longest_k_repeated(s: str, k: int) -> int:\n    \"\"\"Return the length of the longest substring of `s` that occurs\n    at least `k` times.\"\"\"\n    if k > len(s) or k <= 0:\n        return 0\n\n    n = len(s)\n    if n == 0:\n        return 0\n\n    # Suffix array and LCP\n    suffix_array = build_suffix_array(s)\n    lcp = build_lcp(s, suffix_array)\n\n    # Binary search for the longest substring\n    left, right = 0, n\n    while left < right:\n        mid = (left + right + 1) // 2\n        if has_repeated_substring(s, mid, k):\n            left = mid\n        else:\n            right = mid - 1\n\n    return left\n\ndef build_suffix_array(s: str) -> list:\n    # Implement suffix array construction\n    pass\n\ndef build_lcp(s: str, suffix_array: list) -> list:\n    # Implement LCP array construction\n    pass\n\ndef has_repeated_substring(s: str, length: int, k: int) -> bool:\n    # Check if there is a substring of given length that occurs at least k times\n    pass\n\n# Test cases\ndef test_longest_k_repeated():\n    assert longest_k_repeated(\"banana\", 2) == 3    # \"ana\" occurs at 1 and 3 (overlap)\n    assert longest_k_repeated(\"banana\", 3) == 1    # only single chars occur >= 3 times\n    assert longest_k_repeated(\"banana\", 4) == 0\n    assert longest_k_repeated(\"aaa\", 2) == 2       # \"aa\" at 0 and 1\n    assert longest_k_repeated(\"aaa\", 3) == 1       # \"a\" x3\n    assert longest_k_repeated(\"abcabc\", 1) == 6    # whole string, k==1\n    assert longest_k_repeated(\"abcdef\", 2) == 0    # all distinct, nothing repeats\n    assert longest_k_repeated(\"\", 5) == 0\n\ndef test_large_period_two():\n    s = \"ab\" * 50000\n    n = len(s)  # 100000\n    assert longest_k_repeated(s, 2) == 1  # \"ab\" occurs at every consecutive pair\n\ndef test_large_no_long_repeat():\n    # Random over a 10-char alphabet: the longest repeat must be short.\n    rng = random.Random(7)\n    s = \"\".join(rng.choice(\"abcdefghij\") for _ in range(60000))\n    ans = longest_k_repeated(s, 2)\n    # There must be some repeat (pigeonhole on length-1 substrings), and it\n    # should be far shorter than the whole string.\n    assert 1 <= ans < 1000\n\ndef test_single_char_runs():\n    assert longest_k_repeated(\"aaaa\", 2) == 1  # \"a\" x3\n    assert longest_k_repeated(\"aaaaaa\", 3) == 1  # \"a\" x6\n    assert longest_k_repeated(\"aaaaaa\", 4) == 0  # no substring occurs 4 times\n\ndef test_overlapping_counts():\n    assert longest_k_repeated(\"aaaa\", 2) == 3  # \"aa\" occurs at 0 and 1 (overlap)\n    assert longest_k_repeated(\"ababab\", 2) == 2  # \"ab\" occurs at 0, 2, 4\n\ndef test_disjoint_repeat():\n    assert longest_k_repeated(\"abcabc\", 2) == 3  # \"abc\" occurs at 0 and 3\n    assert longest_k_repeated(\"xyzxyz\", 2) == 3  # \"xyz\" occurs at 0 and 3\n\ndef test_mixed_case_sensitive():\n    assert longest_k_repeated(\"AaAa\", 2) == 2  # \"Aa\" occurs at 0 and 1\n    assert longest_k_repeated(\"AaAaAa\", 3) == 2  # \"Aa\" x3\n\ndef test_period_two_medium():\n    s = \"abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab",
    "passed": 0,
    "test_error": "no code extracted from response"
  },
  {
    "total": 1,
    "answer": "```python\ndef longest_k_repeated(s: str, k: int) -> int:\n    \"\"\"Return the length of the longest substring of `s` that occurs\n    at least `k` times.\"\"\"\n    if k > len(s) or k <= 0:\n        return 0\n\n    n = len(s)\n    if n == 0:\n        return 0\n\n    # Suffix array and LCP\n    suffix_array = build_suffix_array(s)\n    lcp = build_lcp(s, suffix_array)\n\n    # Binary search for the longest substring\n    left, right = 0, n\n    while left < right:\n        mid = (left + right + 1) // 2\n        if has_repeated_substring(s, mid, k):\n            left = mid\n        else:\n            right = mid - 1\n\n    return left\n\ndef build_suffix_array(s: str) -> list:\n    # Implement suffix array construction\n    pass\n\ndef build_lcp(s: str, suffix_array: list) -> list:\n    # Implement LCP array construction\n    pass\n\ndef has_repeated_substring(s: str, length: int, k: int) -> bool:\n    # Check if there is a substring of given length that occurs at least k times\n    pass\n\n# Test cases\ndef test_longest_k_repeated():\n    assert longest_k_repeated(\"banana\", 2) == 3    # \"ana\" occurs at 1 and 3 (overlap)\n    assert longest_k_repeated(\"banana\", 3) == 1    # only single chars occur >= 3 times\n    assert longest_k_repeated(\"banana\", 4) == 0\n    assert longest_k_repeated(\"aaa\", 2) == 2       # \"aa\" at 0 and 1\n    assert longest_k_repeated(\"aaa\", 3) == 1       # \"a\" x3\n    assert longest_k_repeated(\"abcabc\", 1) == 6    # whole string, k==1\n    assert longest_k_repeated(\"abcdef\", 2) == 0    # all distinct, nothing repeats\n    assert longest_k_repeated(\"\", 5) == 0\n\ndef test_large_period_two():\n    s = \"ab\" * 50000\n    n = len(s)  # 100000\n    assert longest_k_repeated(s, 2) == 1  # \"ab\" occurs at every consecutive pair\n\ndef test_large_no_long_repeat():\n    # Random over a 10-char alphabet: the longest repeat must be short.\n    rng = random.Random(7)\n    s = \"\".join(rng.choice(\"abcdefghij\") for _ in range(60000))\n    ans = longest_k_repeated(s, 2)\n    # There must be some repeat (pigeonhole on length-1 substrings), and it\n    # should be far shorter than the whole string.\n    assert 1 <= ans < 1000\n\ndef test_single_char_runs():\n    assert longest_k_repeated(\"aaaa\", 2) == 1  # \"a\" x3\n    assert longest_k_repeated(\"aaaaaa\", 3) == 1  # \"a\" x6\n    assert longest_k_repeated(\"aaaaaa\", 4) == 0  # no substring occurs 4 times\n\ndef test_overlapping_counts():\n    assert longest_k_repeated(\"aaaa\", 2) == 3  # \"aa\" occurs at 0 and 1 (overlap)\n    assert longest_k_repeated(\"ababab\", 2) == 2  # \"ab\" occurs at 0, 2, 4\n\ndef test_disjoint_repeat():\n    assert longest_k_repeated(\"abcabc\", 2) == 3  # \"abc\" occurs at 0 and 3\n    assert longest_k_repeated(\"xyzxyz\", 2) == 3  # \"xyz\" occurs at 0 and 3\n\ndef test_mixed_case_sensitive():\n    assert longest_k_repeated(\"AaAa\", 2) == 2  # \"Aa\" occurs at 0 and 1\n    assert longest_k_repeated(\"AaAaAa\", 3) == 2  # \"Aa\" x3\n\ndef test_period_two_medium():\n    s = \"abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab",
    "passed": 0,
    "test_error": ""
  }
]