CSES - 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ä ac saadaan kerättyä vähintään k kappaletta?

Voit olettaa, että merkkijono muodostuu merkeistä ac, 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.