Annettuna on merkkijono, jonka jokainen merkki on 0 tai 1. Tehtäväsi on laskea, monellako tavalla merkkijonon voi halkaista kahteen osaan niin, että molemmissa osissa merkkien 0 ja 1 määrät ovat samat.
Esimerkiksi merkkijonossa 010101 on kaksi halkaisutapaa 01+0101 ja 0101+01. Osassa 01 kumpikin merkki 0 ja 1 esiintyy kerran ja osassa 0101 kumpikin merkki 0 ja 1 esiintyy kahdesti.
Toteuta tiedostoon bitsplit.py funktio count_splits, jolle annetaan parametrina merkkijono. Funktio palauttaa halkaisutapojen määrän.
Sinun tulee toteuttaa tehokas ratkaisu, jonka aikavaativuus on O(n). Et voi esimerkiksi käydä jokaisen mahdollisen halkaisutavan kohdalla vasemman ja oikean osan merkkejä läpi.
Tehtäväpohjan viimeisessä testissä merkkijono sisältää 10^5 kertaa merkit 01. Funktiosi tulee toimia tehokkaasti tässäkin tapauksessa.
def count_splits(sequence):
# TODO
if __name__ == "__main__":
print(count_splits("00")) # 0
print(count_splits("01")) # 0
print(count_splits("0110")) # 1
print(count_splits("010101")) # 2
print(count_splits("000111")) # 0
print(count_splits("01100110")) # 3
sequence = "01"*10**5
print(count_splits(sequence)) # 99999