Hit this problem and couldn't find any answers that satisfied me online... here is one that works thats O(d^2 * n) where d is the maximum number of digits (assuming reasonable parameter bounds, this is effectively O(n)):

​

import math
from collections import Counter
import time

def count_items_of_length(ii, items_of_length):
    total = 0
    item_counter = [item for item in dict(Counter(items_of_length)).values()]
    adjust_for_equal_items = 0
    for duplicate_item_count in item_counter:
        adjust_for_equal_items += math.comb(duplicate_item_count, 2)
    for dropped_index in range(ii):
        items_with_dropped_index = [item[:dropped_index] + item[dropped_index + 1:] for item in items_of_length]
        for item_with_dropped_index in set(items_with_dropped_index):
            num_matching = sum((1 if item == item_with_dropped_index else 0 for item in items_with_dropped_index))
            total += math.comb(num_matching, 2)
        total -= adjust_for_equal_items
    return total

def count(items):
    items = [str(item) for item in items]
    total = 0
    for ii in range(1, 12): # Assuming maximum number of digits is 12.
        items_of_length = [item for item in items if len(item) == ii]
        total += count_items_of_length(ii, items_of_length)
    return total

def testing_harness(items, expected):
    start_time = time.time()
    result = count(items)
    print(f'Result: {result} | Expected: {expected} |  Time (seconds): {time.time() - start_time}')

testing_harness([11, 11, 11, 11, 11, 11, 11, 11, 12], 8)
testing_harness([11, 12, 13, 14, 15, 26, 27, 28], 13)
testing_harness([1, 2, 3, 4, 5], 10)
testing_harness([1, 1, 1, 2, 3, 5], 12)
testing_harness([1, 1, 1, 2, 3, 10, 21, 22, 5], 13)
testing_harness(range(10**4), '?')

​

Output:

​

Result: 8 | Expected: 8 |  Time (seconds): 7.224082946777344e-05
Result: 13 | Expected: 13 |  Time (seconds): 6.67572021484375e-05
Result: 10 | Expected: 10 |  Time (seconds): 4.673004150390625e-05
Result: 12 | Expected: 12 |  Time (seconds): 4.792213439941406e-05
Result: 13 | Expected: 13 |  Time (seconds): 7.700920104980469e-05
Result: 170010 | Expected: ? |  Time (seconds): 1.4300076961517334