Promising String (easy version) (Codeforces 1660F1)
Tags: Math, strings

This is the easy 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 500$$$) —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 3000$$$): 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 $$$3000$$$.

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):
tst = int(input())
for _ in range(tst):
    n = int(input())
    s = input()
    f = [0 for i in range(3)]
    cur_bal = n
    cnt_bal = [0 for i in range(2 * n + 1)]
    cnt_bal[cur_bal] += 1
    f[cur_bal % 3] += 1
    ans = 0
    for i in range(n):
        new_bal = cur_bal
        if s[i] == '-':
            new_bal -= 1
            f[new_bal % 3] += cnt_bal[new_bal]
            ans += f[new_bal % 3]
            cnt_bal[new_bal] += 1
            f[new_bal % 3] += 1
        else:
            f[new_bal % 3] -= cnt_bal[new_bal]
            new_bal += 1
            ans += f[new_bal % 3]
            cnt_bal[new_bal] += 1
            f[new_bal % 3] += 1
        cur_bal = new_bal
    print(ans)

Solution (Python):
tst = int(input())
for _ in range(tst):
    n = int(input())
    s = input()
    f = [0 for i in range(3)]
    cur_bal = n
    cnt_bal = [0 for i in range(2 * n + 1)]
    cnt_bal[cur_bal] += 1
    f[cur_bal % 3] += 1
    ans = 0
    for i in range(n):
        new_bal = cur_bal
        if s[i] == '-':
            new_bal -= 1
            f[new_bal % 3] += cnt_bal[new_bal]
            ans += f[new_bal % 3]
            cnt_bal[new_bal] += 1
            f[new_bal % 3] += 1
        else:
            f[new_bal % 3] -= cnt_bal[new_bal]
            new_bal += 1
            ans += f[new_bal % 3]
            cnt_bal[new_bal] += 1
            f[new_bal % 3] += 1
        cur_bal = new_bal
    print(ans)

Solution (Python):
import collections
for _ in range(int(input())):
    n = int(input())
    l = 2 * n + 2
    s = input().strip()
    y = [[0] * (l + 1) for i in range(3)]

    def upd(x, a):
        while x <= l:
            a[x] += 1
            x += x & -x

    def qry(x, a):
        r = 0
        while x > 0:
            r += a[x]
            x -= x & -x
        return r
    ans = 0
    t = n + 1
    upd(t, y[t % 3])
    for i in s:
        t = t + (1 if i == '-' else -1)
        ans += qry(t, y[t % 3])
        upd(t, y[t % 3])
    print(ans)