Voit olettaa, että merkkijono muodostuu merkeistä
a
–z
, siinä on enintään $10^5$ merkkiä ja kielletty merkki on jokin merkeistä a
–z
. Tavoitteena on, että algoritmin aikavaativuus on $O(n)$.Toteuta tiedostoon
forbidden.py
funktio count
, joka palauttaa halutun tuloksen.def count(s, c): # TODO if __name__ == "__main__": print(count("abacabb", "b")) # 7 print(count("abcdef", "g")) # 21 print(count("xxxxxxxxx", "x")) # 0 print(count("pupujussikainen", "u")) # 48Selitys: Esimerkiksi merkkijonossa
abacabb
on 7 osajonoa, jotka eivät sisällä merkkiä b
:-
a
(kolmesti)
-
c
-
ac
-
ca
-
aca