Bittijako

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