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.