BalancedSubstrings

This problem deals with binary strings: strings in which each character is either '0' or '1'. The characters are interpreted as zeros and ones.

Assume that we have a binary string of length N. Imagine the string as a horizontal lever of length N-1. The weight of the lever is negligible. On the lever, the points with integer coordinates are numbered from 0 (one end of the lever) to N-1 (the other end). Our string represents the distribution of weights on this lever. For each i, if character i of our string is '0', the corresponding point is empty, and if the character is '1', there is a unit weight at that point. Suppose that we place a fulcrum under the point number i. We say that element i of the string is a balance point if the lever is balanced on the fulcrum: the moments of force on either side cancel each other out. A string is called a balanced string if it has at least one balance point. Note that the balance point must be one of the marked points (see examples below).

A formal definition follows. For each valid index i we can compute the torque at i as follows:

1. For each element to the left of i, take its value, multiply it by its distance from i, and add all those results together to obtain the value A.
2. For each element to the right of i, take its value, multiply it by its distance from i, and add all those results together to obtain the value B.
3. The torque at i is computed as (A - B).

We say that index i is a balance point if the torque at i is exactly zero. (Note that the value of the element at index i isn't used in the definition and therefore it can be arbitrary.)

For example, the string "10100001" is a balanced string. Its balance point is the (0-based) index i=3. If we put the fulcrum under the lever at this position, we see "101" to the left and "0001" to the right. On the left side we get A = 1*3 + 0*2 + 1*1 = 4, and on the right side we get B = 0*1 + 0*2 + 0*3 + 1*4 = 4, hence A-B is exactly zero.

The string "0001" is also a balanced string, as its last character is a balance point. The string "11" is not a balanced string, as neither of its two characters is a balance point.

You are given a String s that is a binary string. Return the number of nonempty substrings of s that are balanced.

Substrings that consist of the same characters but occur elsewhere in s are considered different substrings. If they are balanced, each of them should be counted separately. For example, the string "00000" contains four distinct occurrences of the substring "00".