Poistot

Sinulle annetaan merkkijono, joka koostuu vain merkeistä a, b tai c. Voit kerätä merkkejä merkkijonosta poistamalla niitä joko merkkijonon alusta tai lopusta. Kuinka monta merkkiä on vähintään poistettava, jotta jokaista merkkiä a–c saadaan kerättyä vähintään $k$ kappaletta?

Voit olettaa, että merkkijono muodostuu merkeistä a–c, siinä on enintään $10^5$ merkkiä ja kutakin merkkiä on vähintään $k$ kappaletta. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$.

Toteuta tiedostoon removals.py funktio find, joka kertoo, montako merkkiä on vähintään poistettava.

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

Selitys: Merkkijonosta aaaabbbcccc on poistettava vähintään $6$ merkkiä, jotta saamme kerättyä kutakin merkkiä vähintään yhden kappaleen. Yksi mahdollinen tapa on poistaa $5$ merkkiä merkkijonon alusta ja $1$ merkki merkkijonon lopusta. Olisi myös mahdollista poistaa $5$ merkkiä lopusta ja $1$ alusta.