[Python] How to create the largest number from an array of integers with no more than 'k'...

I have an array of integers ranging from 0 to 9, and I need to create the largest possible number by concatenating these integers. However, there's a constraint: I cannot have more than 'k' consecutive identical digits in the resulting number. Ideally this problem should be solven in O(n)

Constraints and Requirements: Without the use of additional libraries The input array consists only of single poisitve digit integers. The output should be the largest possible number formed by concatenating elements of the array. No more than 'k' consecutive identical elements should appear in the output. All arrays are solvable, e,g [1,1,1,1,1] k=2 cannot exist.

test_cases = [
# Format: (k, [array_of_integers], "expected_result")
(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:

# Step 1: Count frequencies
freq = {}
for num in arr:
if num in freq:
freq[num] += 1
else:
freq[num] = 1

# Step 2: Sort the digits in descending order
digits = sorted(freq.keys(), reverse=True)

result = []
last_digit = None
last_count = 0

# Step 3: Build the result
while any(freq[d] > 0 for d in digits):
placed = False
# Try to place the largest available digit first
for digit in digits:
if freq[digit] == 0:
continue # Skip if this digit is already used up
if digit == last_digit and last_count == k:
continue # Skip if placing this digit violates the k constraint

# Determine how many times we can place this digit
use_count = min(freq[digit], k if digit != last_digit else k - last_count)
result.extend([digit] * use_count)
freq[digit] -= use_count

# Update the last_digit and last_count
if digit == last_digit:
last_count += use_count
else:
last_digit = digit
last_count = use_count

placed = True
break # After placing, try the largest digit again

if not placed:
# Step 4: Break the sequence with the next highest different digit
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 no placement is possible, break out
if not placed:
break

# Convert result list to a string
result_str = ''.join(map(str, result))
return result_str




>>> Test Case 1: **Fail**
Input: 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]
Output: 9996669966444344211101
Expected: 999699666464443431110

>>> Test Case 2: **Pass**
Input: k: 1, n: [1, 2, 3, 4, 5]
Output: 54321
Expected: 54321

>>> Test Case 3: **Pass**
Input: k: 2, n: [1, 1, 2, 2, 3, 3]
Output: 332211
Expected: 332211

>>> Test Case 4: **Pass**
Input: k: 2, n: [9, 9, 8, 8, 7, 7]
Output: 998877
Expected: 998877

>>> Test Case 5: **Fail**
Input: k: 3, n: [5, 5, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3]
Output: 55544454333
Expected: 555444333555444333

>>> Test Case 6: **Fail**
Input: k: 2, n: [2, 2, 2, 2, 1, 1, 1, 1, 0, 0, 0, 0]
Output: 2211221100
Expected: 221100221100

>>> Test Case 7: **Pass**
Input: k: 3, n: [9, 9, 9, 9, 9, 9, 8, 8, 8, 8, 8, 8]
Output: 999888999888
Expected: 999888999888

>>> Test Case 8: **Pass**
Input: k: 1, n: [9, 8, 7, 6, 5]
Output: 98765
Expected: 98765

>>> Test Case 9: **Fail**
Input: k: 3, n: [1, 1, 1, 1, 1, 1]
Output: 111
Expected: 111111

>>> Test Case 10: **Fail**
Input: k: 2, n: [4, 4, 4, 3, 3, 3, 2, 2, 2, 1, 1, 1]
Output: 443343221121
Expected: 443322114321

Continue reading...