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)) # 13Selitys: 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.