CSES - Bit split

You are given a string where each character is 0 or 1. Your task is to count how many ways the string can be split into two parts so that in both parts the number of 0s is equal to the number of 1s.

For example, the string 010101 has two valid splits: 01+0101 and 0101+01. In the part 01, both 0 and 1 occur once, and in the part 0101, both 0 and 1 occur twice.

In a file bitsplit.py, implement the function count_splits that takes the list of numbers as a parameter and returns the count of valid splits.

You must implement an efficient solution with a time complexity O(n)O(n). For example, you cannot afford to test each possible split position separately.

In the last test case of the following code template, the string contains 10510^5 copies of the string 01. Your function should finish quickly in this test case too.

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