Google OA 2023 - More ones

You are given a string S that consists only of 0's and 1's.

Determine the number of substrings that have more 1's than 0's

Note: A substring of a string is a sequence obtained by removing zero or more characters from either/both the front and back of the string. The substrings of string "101" are ["101", "10", "1", "0" "01", "1"]. "11" cannot be called the substring of "101" because it cannot be obtained by removing characters from the front or back of "101"

Example: S="0111"

Approach

The substrings of "0111" that have more 1's than 0's are

["011", "0111", "1", "11", "111", "1" "11", "1"]

Therefore, the answer is 8 substrings.

Function description

Complete the solve function provided in the editor. This function

Input format

Note: This is the input format that you must use to provide custom input (available above the Compile and Test button).

• The first line contains a single integer T that denotes the number of test cases. T also denotes the number of times you have to run the solve function on a different set of inputs.
• The next T lines contain a string denoting S.

Output format

For each of the test cases, print an integer value in a new line representing the count of the substrings that have more 1's than 0's.

Constraints
1≤T≤ 10
1≤|S|≤ 10^6
S consists of only '1' and '0'

Sample Input 

2
1010
0111

Sample output

3
8

Explanation

Test Case 1: S="1010"

The substrings that have more '1' than '0' are [ "1", "1", "101"]. Hence, the answer is 3.

Test Case 2: The number of substrings is 8. Explanation is given in the above example.