count K most frequent items

from collections import Counter


SEQ = 'XYYZYYXYYZYY'
K = 2


def build_in(sequence, k):
    c = Counter(sequence).most_common(k)
    return dict(c)

def frequent(sequence, k):
    counters = {}
    for item in sequence:
        if len(counters) < k:
            counters[item] = counters.get(item, 0) + 1
        elif item in counters:
            counters[item] += 1
        else:
            for key in counters:
                counters[key] -= 1
            counters = {key: value for key, value in counters.items() if value != 0}
    return counters

def space_saving(sequence, k):
    counters = {}
    for item in sequence:
        if len(counters) < k:
            counters[item] = counters.get(item, 0) + 1
        elif item in counters:
            counters[item] += 1
        else:
            least_frequent_item = min(counters, key=counters.get)
            least_frequent_item_count = counters.pop(least_frequent_item)
            counters[item] = least_frequent_item_count + 1
    return counters


implementations = [build_in, frequent, space_saving]
for implementation in implementations:
    print('[{}]'.format(implementation.__name__))
    print(implementation(SEQ, K))


# [build_in]
# {'Y': 8, 'X': 2}
# [frequent]
# {'Y': 6}
# [space_saving]
# {'Y': 8, 'Z': 4}