Как создать наибольшее число из массива целых чисел, не имея более ‘k’ последовательных идентичных элементов?

У меня есть массив целых чисел от 0 до 9, и мне нужно создать максимально возможное число, объединяя эти целые числа. Однако есть ограничение: я не могу иметь более ‘k’ последовательных одинаковых цифр в полученном числе. В идеале эту задачу следует решить за O(n)

Ограничения и требования:
Без использования дополнительных библиотек
Входной массив состоит только из положительных одноцифровых целых чисел.
Выходным результатом должно быть максимально возможное число, сформированное путем объединения элементов массива.
Не более ‘k’ последовательных одинаковых элементов должно быть в выходных данных.
Все массивы разрешимы, например [1,1,1,1,1] k=2 не могут существовать.

test_cases = [
    # Формат: (k, [массив_целых_чисел], "ожидаемый_результат")
        (3, [0, 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 9, 9, 9, 9, 9], "999699666464443431110"),
        (1, [1, 2, 3, 4, 5], "54321"),
        (2, [1, 1, 2, 2, 3, 3], "332211"),
        (2, [9, 9, 8, 8, 7, 7], "998877"),
        (3, [5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3], "555444333555444333"),
        (2, [2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0], "221100221100"),
        (3, [9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8], "999888999888"),
        (1, [9, 8, 7, 6, 5], "98765"),
        (3, [1, 1, 1, 1, 1, 1], "111111"),
        (2, [4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1], "443322114321"),
        (2, [9, 9, 8, 8, 7, 7, 6, 6], "99887766"),
        (3, [0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2], "222111000222111000"),
        (2, [5, 5, 5, 4, 4, 4, 3, 3, 3], "554433554433"),
        (1, [1, 2, 3, 4, 5, 6], "654321"),
        (3, [6, 6, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4], "666555444666555444"),
        (2, [9, 8, 7, 6, 5, 4], "998877665544"),
        (3, [3, 3, 3, 2, 2, 2, 1, 1, 1], "333222111"),
        (2, [4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2], "443322443322"),
        (3, [9, 9, 9, 8, 8, 8, 7, 7, 7, 6, 6, 6, 5, 5, 5], "999888777666555"),
        (2, [0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5], "554433221100"),
        (2, [9, 9, 9, 9, 8, 8, 8, 8, 7, 7, 7, 7], "998877998877"),
        (1, [2, 2, 1, 1, 0, 0], "210210"),
        (2, [3, 3, 3, 2, 2, 2, 1, 1, 1], "332211321"),
        (2, [5, 5, 5, 4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1], "55443322154321")
]

def largestNumberWithoutKConsecutive(arr: list, k: int) -> str:

    # Шаг 1: Подсчет частот
    freq = {}
    for num in arr:
        if num in freq:
            freq[num] += 1
        else:
            freq[num] = 1

    # Шаг 2: Сортировка цифр по убыванию
    digits = sorted(freq.keys(), reverse=True)

    result = []
    last_digit = None
    last_count = 0

    # Шаг 3: Построение результата
    while any(freq[d] > 0 for d in digits):
        placed = False
        # Попробуем поставить самую большую доступную цифру
        for digit in digits:
            if freq[digit] == 0:
                continue  # Пропустить, если эта цифра уже использована
            if digit == last_digit and last_count == k:
                continue  # Пропустить, если установка этой цифры нарушает ограничение k

            # Определяем, сколько раз мы можем установить эту цифру
            use_count = min(freq[digit], k if digit != last_digit else k - last_count)
            result.extend([digit] * use_count)
            freq[digit] -= use_count

            # Обновляем last_digit и last_count
            if digit == last_digit:
                last_count += use_count
            else:
                last_digit = digit
                last_count = use_count

            placed = True
            break  # После установки пытаемся снова вставить первую по величине цифру

        if not placed:
            # Шаг 4: Разрываем последовательность следующей самой высокой другой цифрой
            for digit in digits:
                if freq[digit] > 0 and digit != last_digit:
                    result.append(digit)
                    freq[digit] -= 1
                    last_digit = digit
                    last_count = 1
                    placed = True
                    break
            # Если нет возможности для установки, прерываем
            if not placed:
                break

    # Преобразуем список результата в строку
    result_str="".join(map(str, result))
    return result_str

>>> Тестовый случай 1: **Провал**  
Входные данные: k: 3, n: [0, 1, 1, 1, 1, 2, 3, 4, 4, 4, 4, 4, 6, 6, 6, 6, 6, 9, 9, 9, 9, 9]  
Выход: 9996669966444344211101  
Ожидаемый: 999699666464443431110

>>> Тестовый случай 2: **Успех**  
Входные данные: k: 1, n: [1, 2, 3, 4, 5]  
Выход: 54321  
Ожидаемый: 54321

>>> Тестовый случай 3: **Успех**  
Входные данные: k: 2, n: [1, 1, 2, 2, 3, 3]  
Выход: 332211  
Ожидаемый: 332211

>>> Тестовый случай 4: **Успех**  
Входные данные: k: 2, n: [9, 9, 8, 8, 7, 7]  
Выход: 998877  
Ожидаемый: 998877

>>> Тестовый случай 5: **Провал**  
Входные данные: k: 3, n: [5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3]  
Выход: 55544454333  
Ожидаемый: 555444333555444333

>>> Тестовый случай 6: **Провал**  
Входные данные: k: 2, n: [2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0]  
Выход: 2211221100  
Ожидаемый: 221100221100

>>> Тестовый случай 7: **Успех**  
Входные данные: k: 3, n: [9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8]  
Выход: 999888999888  
Ожидаемый: 999888999888

>>> Тестовый случай 8: **Успех**  
Входные данные: k: 1, n: [9, 8, 7, 6, 5]  
Выход: 98765  
Ожидаемый: 98765

>>> Тестовый случай 9: **Провал**  
Входные данные: k: 3, n: [1, 1, 1, 1, 1, 1]  
Выход: 111  
Ожидаемый: 111111

>>> Тестовый случай 10: **Провал**  
Входные данные: k: 2, n: [4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1]  
Выход: 443343221121  
Ожидаемый: 443322114321