Promising String (hard version) (Codeforces 1660F2)
Tags: Math, strings

This is the hard version of Problem F. The only difference between the easy version and the hard version is the constraints.We will call a non-empty string balanced if it contains the same number of plus and minus signs. For example: strings "+--+" and "++-+--" are balanced, and strings "+--", "--" and "" are not balanced.We will call a string promising if the string can be made balanced by several (possibly zero) uses of the following operation:  replace two adjacent minus signs with one plus sign. In particular, every balanced string is promising. However, the converse is not true: not every promising string is balanced.For example, the string "-+---" is promising, because you can replace two adjacent minuses with plus and get a balanced string "-++-", or get another balanced string "-+-+".How many non-empty substrings of the given string $$$s$$$ are promising? Each non-empty promising substring must be counted in the answer as many times as it occurs in string $$$s$$$.Recall that a substring is a sequence of consecutive characters of the string. For example, for string "+-+" its substring are: "+-", "-+", "+", "+-+" (the string is a substring of itself) and some others. But the following strings are not its substring: "--", "++", "-++".

Input: The first line of the input contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) —the number of test cases in the test.Then the descriptions of test cases follow.Each test case of input data consists of two lines. The first line consists of the number $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$): the length of $$$s$$$.The second line of the test case contains the string $$$s$$$ of length $$$n$$$, consisting only of characters "+" and "-".It is guaranteed that the sum of values $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, print a single number: the number of the promising non-empty substrings of string $$$s$$$. Each non-empty promising substring must be counted in the answer as many times as it occurs in string $$$s$$$.

Note: The following are the promising substrings for the first three test cases in the example:  $$$s[1 \dots 2]$$$="+-", $$$s[2 \dots 3]$$$="-+";  $$$s[1 \dots 2]$$$="-+", $$$s[2 \dots 3]$$$="+-", $$$s[1 \dots 5]$$$="-+---", $$$s[3 \dots 5]$$$="---";  $$$s[1 \dots 3]$$$="---", $$$s[2 \dots 4]$$$="---". 

Sample Inputs:
5
3
+-+
5
-+---
4
----
7
--+---+
6
+++---

Sample Outputs:
2
4
2
7
4

Solution (Python):
for _ in range(int(input())):
    f = [0] * 3
    count = [0] * (2 * int(input()) + 1)
    u = 0
    count[u] += 1
    f[u % 3] += 1
    ans = 0
    for x in input():
        if x == '-':
            u -= 1
            f[u % 3] += count[u]
        else:
            f[u % 3] -= count[u]
            u += 1
        ans += f[u % 3]
        count[u] += 1
        f[u % 3] += 1
    print(ans)

Solution (Python):
for _ in range(int(input())):
    f = [0] * 3
    count = [0] * (2 * int(input()) + 1)
    u = 0
    count[u] += 1
    f[u % 3] += 1
    ans = 0
    for x in input():
        if x == '-':
            u -= 1
            f[u % 3] += count[u]
        else:
            f[u % 3] -= count[u]
            u += 1
        ans += f[u % 3]
        count[u] += 1
        f[u % 3] += 1
    print(ans)

Solution (Python):
def solve():
    n = int(input())
    s = input()
    res = 0
    cnt = [0 for _ in range(2 * n + 1)]
    cnt_promise = [0] * 3
    cur_bal = n
    cnt[cur_bal] = 1
    cnt_promise[cur_bal % 3] = 1
    for c in s:
        new_bal = cur_bal
        if c == '-':
            new_bal -= 1
            cnt_promise[new_bal % 3] += cnt[new_bal]
            res += cnt_promise[new_bal % 3]
            cnt[new_bal] += 1
            cnt_promise[new_bal % 3] += 1
        else:
            cnt_promise[new_bal % 3] -= cnt[new_bal]
            new_bal += 1
            res += cnt_promise[new_bal % 3]
            cnt_promise[new_bal % 3] += 1
            cnt[new_bal] += 1
        cur_bal = new_bal
    print(res)
num_test = int(input())
for t in range(num_test):
    solve()