Removals

You are given a string that consists of the characters a, b and c. You can collect characters by removing them from either the beginning of the string or from the end of the string. What is the smallest number of characters that must be removed in order to collect at least k of each character a–c?

You may assume that the string consists of the characters a–c, that the length of the string is at most 10^5, and that each character occurs at least k times. The goal is an algorithm with time complexity O(n).

In a file removals.py, implement a function find that returns the minimum number of characters to remove.

def find(s, k):
    # TODO

if __name__ == "__main__":
    print(find("abc", 1)) # 3
    print(find("aabca", 1)) # 3
    print(find("aaaabbbcccc", 1)) # 6
    print(find("aabbaacc", 2)) # 6
    print(find("aaaabbbbaaaccccaaccacbbaa", 3)) # 13

Explanation: In the string aaaabbbcccc, at least 6 characters must be removed to collect at least one of each character. One possibility is to remove 5 characters from the beginning and one from the end. Or we could remove the last 5 characters and one from the beginning.