Plus-Minus Split (Codeforces 1919B)
Tags: Greedy, greedy

You are given a string $$$s$$$ of length $$$n$$$ consisting of characters "+" and "-". $$$s$$$ represents an array $$$a$$$ of length $$$n$$$ defined by $$$a_i=1$$$ if $$$s_i=$$$ "+" and $$$a_i=-1$$$ if $$$s_i=$$$ "-".You will do the following process to calculate your penalty:   Split $$$a$$$ into non-empty arrays $$$b_1,b_2,\ldots,b_k$$$ such that $$$b_1+b_2+\ldots+b_k=a^\dagger$$$, where $$$+$$$ denotes array concatenation.  The penalty of a single array is the absolute value of its sum multiplied by its length. In other words, for some array $$$c$$$ of length $$$m$$$, its penalty is calculated as $$$p(c)=|c_1+c_2+\ldots+c_m| \cdot m$$$.  The total penalty that you will receive is $$$p(b_1)+p(b_2)+\ldots+p(b_k)$$$. If you perform the above process optimally, find the minimum possible penalty you will receive.$$$^\dagger$$$ Some valid ways to split $$$a=[3,1,4,1,5]$$$ into $$$(b_1,b_2,\ldots,b_k)$$$ are $$$([3],[1],[4],[1],[5])$$$, $$$([3,1],[4,1,5])$$$ and $$$([3,1,4,1,5])$$$ while some invalid ways to split $$$a$$$ are $$$([3,1],[1,5])$$$, $$$([3],[\,],[1,4],[1,5])$$$ and $$$([3,4],[5,1,1])$$$.

Input: Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the length of string $$$s$$$.The second line of each test case contains string $$$s$$$ ($$$s_i \in \{ \mathtt{+}, \mathtt{-} \}$$$, $$$|s| = n$$$).Note that there are no constraints on the sum of $$$n$$$ over all test cases.

Output: For each test case, output a single integer representing the minimum possible penalty you will receive.

Note: In the first test case, we have $$$a=[1]$$$. We can split array $$$a$$$ into $$$([1])$$$. Then, the sum of penalties of the subarrays is $$$p([1]) = 1$$$.In the second test case, we have $$$a=[-1,-1,-1,-1,-1]$$$. We can split array $$$a$$$ into $$$([-1],[-1],[-1],[-1],[-1])$$$. Then, the sum of penalties of the subarrays is $$$p([-1]) + p([-1]) + p([-1]) + p([-1]) + p([-1]) = 1 + 1 + 1 + 1 + 1 = 5$$$.In the third test case, we have $$$a=[1,-1,1,-1,1,-1]$$$. We can split array $$$a$$$ into $$$([1,-1,1,-1],[1,-1])$$$. Then, the sum of penalties of the subarrays is $$$p([1,-1,1,-1]) + p([1,-1]) = 0 + 0 = 0$$$.

Sample Inputs:
5
1
+
5
-----
6
+-+-+-
10
--+++++++-
20
+---++++-+++++---++-

Sample Outputs:
1
5
0
4
4

Solution (Python):
for s in [*open(0)][2::2]:
    f = s.count
    print(abs(f('+') - f('-')))

Solution (Python):
for s in [*open(0)][2::2]:
    f = s.count
    print(abs(f('+') - f('-')))

Solution (Python):
for p in [*open(0)][2::2]:
    print(abs(len(p) - 2 * p.count('+') - 1))