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."""
    n = len(s)
    if n == 0:
        return 0
    
    # We use a suffix automaton (SAM) to efficiently count occurrences
    # of all substrings in O(n) time and O(n) space.
    # The SAM is built for the string s.
    
    # Each state in the SAM has:
    # - len: the length of the longest string in this state's equivalence class
    # - link: the suffix link (points to the state representing the longest proper suffix)
    # - next: a dictionary mapping characters to the next state
    
    # Initialize the SAM with the first character
    # State 0: the initial state (empty string)
    # State 1: the state representing the single character 'a'
    size = 1
    last = 0
    # We use a list of dictionaries for transitions to handle arbitrary Unicode
    nexts = [{}]
    link = [-1]
    length = [0]
    
    for ch in s:
        # Create a new state for the current character
        cur = size
        size += 1
        nexts.append({})
        link.append(0)
        length.append(length[last] + 1)
        
        # Add the transition from the last state to the new state via the current character
        p = last
        while p != -1 and ch not in nexts[p]:
            nexts[p][ch] = cur
            p = link[p]
        
        if p == -1:
            # The character was not found in any previous state, so the suffix link is 0
            link[cur] = 0
        else:
            q = nexts[p][ch]
            if length[p] + 1 == length[q]:
                # The transition already exists and is correct
                link[cur] = q
            else:
                # We need to clone the state q
                clone = size
                size += 1
                nexts.append(nexts[q].copy())
                link.append(link[q])
                length.append(length[p] + 1)
                
                # Update the suffix link of q and the new state cur
                while p != -1 and nexts[p].get(ch) == q:
                    nexts[p][ch] = clone
                    p = link[p]
                
                link[q] = link[cur] = clone
        
        last = cur
    
    # Now we have the SAM. We need to compute the occurrence count for each state.
    # We do this by processing states in reverse order of their 'len' value.
    # The occurrence count for a state is the number of occurrences of the
    # longest string in its equivalence class.
    
    # Initialize an array to store the occurrence count for each state
    occ = [0] * size
    
    # We'll process states in order of increasing length, but we need to
    # propagate counts from longer states to shorter ones via suffix links.
    # A simple way is to process states in reverse order of their 'len' value.
    
    # We'll use a list to store states sorted by their 'len' value.
    # This is a standard technique for processing SAM states.
    states_by_len = [[] for _ in range(n + 1)]
    for v in range(size):
        states_by_len[length[v]].append(v)
    
    # First, set the occurrence count for the initial state (0) to 1
    # because the empty string occurs once.
    occ[0] = 1
    
    # Then, process states in order of increasing length.
    # For each state, add its occurrence count to the occurrence count of its suffix link.
    # This is because the suffix link represents a suffix of the strings in the current state,
    # and the number of occurrences of the suffix is at least as many as the number of
    # occurrences of the longer string.
    for l in range(1, n + 1):
        for v in states_by_len[l]:
            occ[link[v]] += occ[v]
    
    # Now, we can find the answer.
    # We want the largest L such that there exists a state with length >= L
    # and occurrence count >= k.
    # We can iterate L from n down to 1 and check if any state satisfies the condition.
    
    # We can optimize this by iterating over states in order of decreasing length
    # and checking if their occurrence count >= k.
    # The length of the state is the length of the longest string in its equivalence class.
    # So if a state has length L and occurrence count >= k, then the answer is at least L.
    
    # We'll iterate over states in order of decreasing length.
    # We'll keep track of the maximum length we've seen so far that satisfies the condition.
    
    max_len = 0
    for v in range(size - 1, 0, -1):
        if occ[v] >= k:
            max_len = max(max_len, length[v])
            # We can break early if we find a state with length n, because that's the maximum possible.
            if max_len == n:
                break
    
    return max_len
```

[
  {
    "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    n = len(s)\n    if n == 0:\n        return 0\n    \n    # We use a suffix automaton (SAM) to efficiently count occurrences\n    # of all substrings in O(n) time and O(n) space.\n    # The SAM is built for the string s.\n    \n    # Each state in the SAM has:\n    # - len: the length of the longest string in this state's equivalence class\n    # - link: the suffix link (points to the state representing the longest proper suffix)\n    # - next: a dictionary mapping characters to the next state\n    \n    # Initialize the SAM with the first character\n    # State 0: the initial state (empty string)\n    # State 1: the state representing the single character 'a'\n    size = 1\n    last = 0\n    # We use a list of dictionaries for transitions to handle arbitrary Unicode\n    nexts = [{}]\n    link = [-1]\n    length = [0]\n    \n    for ch in s:\n        # Create a new state for the current character\n        cur = size\n        size += 1\n        nexts.append({})\n        link.append(0)\n        length.append(length[last] + 1)\n        \n        # Add the transition from the last state to the new state via the current character\n        p = last\n        while p != -1 and ch not in nexts[p]:\n            nexts[p][ch] = cur\n            p = link[p]\n        \n        if p == -1:\n            # The character was not found in any previous state, so the suffix link is 0\n            link[cur] = 0\n        else:\n            q = nexts[p][ch]\n            if length[p] + 1 == length[q]:\n                # The transition already exists and is correct\n                link[cur] = q\n            else:\n                # We need to clone the state q\n                clone = size\n                size += 1\n                nexts.append(nexts[q].copy())\n                link.append(link[q])\n                length.append(length[p] + 1)\n                \n                # Update the suffix link of q and the new state cur\n                while p != -1 and nexts[p].get(ch) == q:\n                    nexts[p][ch] = clone\n                    p = link[p]\n                \n                link[q] = link[cur] = clone\n        \n        last = cur\n    \n    # Now we have the SAM. We need to compute the occurrence count for each state.\n    # We do this by processing states in reverse order of their 'len' value.\n    # The occurrence count for a state is the number of occurrences of the\n    # longest string in its equivalence class.\n    \n    # Initialize an array to store the occurrence count for each state\n    occ = [0] * size\n    \n    # We'll process states in order of increasing length, but we need to\n    # propagate counts from longer states to shorter ones via suffix links.\n    # A simple way is to process states in reverse order of their 'len' value.\n    \n    # We'll use a list to store states sorted by their 'len' value.\n    # This is a standard technique for processing SAM states.\n    states_by_len = [[] for _ in range(n + 1)]\n    for v in range(size):\n        states_by_len[length[v]].append(v)\n    \n    # First, set the occurrence count for the initial state (0) to 1\n    # because the empty string occurs once.\n    occ[0] = 1\n    \n    # Then, process states in order of increasing length.\n    # For each state, add its occurrence count to the occurrence count of its suffix link.\n    # This is because the suffix link represents a suffix of the strings in the current state,\n    # and the number of occurrences of the suffix is at least as many as the number of\n    # occurrences of the longer string.\n    for l in range(1, n + 1):\n        for v in states_by_len[l]:\n            occ[link[v]] += occ[v]\n    \n    # Now, we can find the answer.\n    # We want the largest L such that there exists a state with length >= L\n    # and occurrence count >= k.\n    # We can iterate L from n down to 1 and check if any state satisfies the condition.\n    \n    # We can optimize this by iterating over states in order of decreasing length\n    # and checking if their occurrence count >= k.\n    # The length of the state is the length of the longest string in its equivalence class.\n    # So if a state has length L and occurrence count >= k, then the answer is at least L.\n    \n    # We'll iterate over states in order of decreasing length.\n    # We'll keep track of the maximum length we've seen so far that satisfies the condition.\n    \n    max_len = 0\n    for v in range(size - 1, 0, -1):\n        if occ[v] >= k:\n            max_len = max(max_len, length[v])\n            # We can break early if we find a state with length n, because that's the maximum possible.\n            if max_len == n:\n                break\n    \n    return max_len\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.17s"
  },
  {
    "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    n = len(s)\n    if n == 0:\n        return 0\n    \n    # We use a suffix automaton (SAM) to efficiently count occurrences\n    # of all substrings in O(n) time and O(n) space.\n    # The SAM is built for the string s.\n    \n    # Each state in the SAM has:\n    # - len: the length of the longest string in this state's equivalence class\n    # - link: the suffix link (points to the state representing the longest proper suffix)\n    # - next: a dictionary mapping characters to the next state\n    \n    # Initialize the SAM with the first character\n    # State 0: the initial state (empty string)\n    # State 1: the state representing the single character 'a'\n    size = 1\n    last = 0\n    # We use a list of dictionaries for transitions to handle arbitrary Unicode\n    nexts = [{}]\n    link = [-1]\n    length = [0]\n    \n    for ch in s:\n        # Create a new state for the current character\n        cur = size\n        size += 1\n        nexts.append({})\n        link.append(0)\n        length.append(length[last] + 1)\n        \n        # Add the transition from the last state to the new state via the current character\n        p = last\n        while p != -1 and ch not in nexts[p]:\n            nexts[p][ch] = cur\n            p = link[p]\n        \n        if p == -1:\n            # The character was not found in any previous state, so the suffix link is 0\n            link[cur] = 0\n        else:\n            q = nexts[p][ch]\n            if length[p] + 1 == length[q]:\n                # The transition already exists and is correct\n                link[cur] = q\n            else:\n                # We need to clone the state q\n                clone = size\n                size += 1\n                nexts.append(nexts[q].copy())\n                link.append(link[q])\n                length.append(length[p] + 1)\n                \n                # Update the suffix link of q and the new state cur\n                while p != -1 and nexts[p].get(ch) == q:\n                    nexts[p][ch] = clone\n                    p = link[p]\n                \n                link[q] = link[cur] = clone\n        \n        last = cur\n    \n    # Now we have the SAM. We need to compute the occurrence count for each state.\n    # We do this by processing states in reverse order of their 'len' value.\n    # The occurrence count for a state is the number of occurrences of the\n    # longest string in its equivalence class.\n    \n    # Initialize an array to store the occurrence count for each state\n    occ = [0] * size\n    \n    # We'll process states in order of increasing length, but we need to\n    # propagate counts from longer states to shorter ones via suffix links.\n    # A simple way is to process states in reverse order of their 'len' value.\n    \n    # We'll use a list to store states sorted by their 'len' value.\n    # This is a standard technique for processing SAM states.\n    states_by_len = [[] for _ in range(n + 1)]\n    for v in range(size):\n        states_by_len[length[v]].append(v)\n    \n    # First, set the occurrence count for the initial state (0) to 1\n    # because the empty string occurs once.\n    occ[0] = 1\n    \n    # Then, process states in order of increasing length.\n    # For each state, add its occurrence count to the occurrence count of its suffix link.\n    # This is because the suffix link represents a suffix of the strings in the current state,\n    # and the number of occurrences of the suffix is at least as many as the number of\n    # occurrences of the longer string.\n    for l in range(1, n + 1):\n        for v in states_by_len[l]:\n            occ[link[v]] += occ[v]\n    \n    # Now, we can find the answer.\n    # We want the largest L such that there exists a state with length >= L\n    # and occurrence count >= k.\n    # We can iterate L from n down to 1 and check if any state satisfies the condition.\n    \n    # We can optimize this by iterating over states in order of decreasing length\n    # and checking if their occurrence count >= k.\n    # The length of the state is the length of the longest string in its equivalence class.\n    # So if a state has length L and occurrence count >= k, then the answer is at least L.\n    \n    # We'll iterate over states in order of decreasing length.\n    # We'll keep track of the maximum length we've seen so far that satisfies the condition.\n    \n    max_len = 0\n    for v in range(size - 1, 0, -1):\n        if occ[v] >= k:\n            max_len = max(max_len, length[v])\n            # We can break early if we find a state with length n, because that's the maximum possible.\n            if max_len == n:\n                break\n    \n    return max_len\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.16s"
  },
  {
    "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    n = len(s)\n    if n == 0:\n        return 0\n    \n    # We use a suffix automaton (SAM) to efficiently count occurrences\n    # of all substrings in O(n) time and O(n) space.\n    # The SAM is built for the string s.\n    \n    # Each state in the SAM has:\n    # - len: the length of the longest string in this state's equivalence class\n    # - link: the suffix link (points to the state representing the longest proper suffix)\n    # - next: a dictionary mapping characters to the next state\n    \n    # Initialize the SAM with the first character\n    # State 0: the initial state (empty string)\n    # State 1: the state representing the single character 'a'\n    size = 1\n    last = 0\n    # We use a list of dictionaries for transitions to handle arbitrary Unicode\n    nexts = [{}]\n    link = [-1]\n    length = [0]\n    \n    for ch in s:\n        # Create a new state for the current character\n        cur = size\n        size += 1\n        nexts.append({})\n        link.append(0)\n        length.append(length[last] + 1)\n        \n        # Add the transition from the last state to the new state via the current character\n        p = last\n        while p != -1 and ch not in nexts[p]:\n            nexts[p][ch] = cur\n            p = link[p]\n        \n        if p == -1:\n            # The character was not found in any previous state, so the suffix link is 0\n            link[cur] = 0\n        else:\n            q = nexts[p][ch]\n            if length[p] + 1 == length[q]:\n                # The transition already exists and is correct\n                link[cur] = q\n            else:\n                # We need to clone the state q\n                clone = size\n                size += 1\n                nexts.append(nexts[q].copy())\n                link.append(link[q])\n                length.append(length[p] + 1)\n                \n                # Update the suffix link of q and the new state cur\n                while p != -1 and nexts[p].get(ch) == q:\n                    nexts[p][ch] = clone\n                    p = link[p]\n                \n                link[q] = link[cur] = clone\n        \n        last = cur\n    \n    # Now we have the SAM. We need to compute the occurrence count for each state.\n    # We do this by processing states in reverse order of their 'len' value.\n    # The occurrence count for a state is the number of occurrences of the\n    # longest string in its equivalence class.\n    \n    # Initialize an array to store the occurrence count for each state\n    occ = [0] * size\n    \n    # We'll process states in order of increasing length, but we need to\n    # propagate counts from longer states to shorter ones via suffix links.\n    # A simple way is to process states in reverse order of their 'len' value.\n    \n    # We'll use a list to store states sorted by their 'len' value.\n    # This is a standard technique for processing SAM states.\n    states_by_len = [[] for _ in range(n + 1)]\n    for v in range(size):\n        states_by_len[length[v]].append(v)\n    \n    # First, set the occurrence count for the initial state (0) to 1\n    # because the empty string occurs once.\n    occ[0] = 1\n    \n    # Then, process states in order of increasing length.\n    # For each state, add its occurrence count to the occurrence count of its suffix link.\n    # This is because the suffix link represents a suffix of the strings in the current state,\n    # and the number of occurrences of the suffix is at least as many as the number of\n    # occurrences of the longer string.\n    for l in range(1, n + 1):\n        for v in states_by_len[l]:\n            occ[link[v]] += occ[v]\n    \n    # Now, we can find the answer.\n    # We want the largest L such that there exists a state with length >= L\n    # and occurrence count >= k.\n    # We can iterate L from n down to 1 and check if any state satisfies the condition.\n    \n    # We can optimize this by iterating over states in order of decreasing length\n    # and checking if their occurrence count >= k.\n    # The length of the state is the length of the longest string in its equivalence class.\n    # So if a state has length L and occurrence count >= k, then the answer is at least L.\n    \n    # We'll iterate over states in order of decreasing length.\n    # We'll keep track of the maximum length we've seen so far that satisfies the condition.\n    \n    max_len = 0\n    for v in range(size - 1, 0, -1):\n        if occ[v] >= k:\n            max_len = max(max_len, length[v])\n            # We can break early if we find a state with length n, because that's the maximum possible.\n            if max_len == n:\n                break\n    \n    return max_len\n```",
    "passed": 2,
    "test_error": ""
  }
]