Schrodinger Smiley CodeChef Solution 2023

Problem

In the realm of emoticons, the Schrödinger smiley both smiles and frowns until its state is observed.

Given a string $�$ consisting only of :, (, and ) (colon, right parenthesis, and left parenthesis).
We define a Schrödinger's Smiley as any positive number of right parenthesis between two colons. For example, :):, :))):, and :))))): are Schrödinger's smileys while :))(:, :(:, ::): and :: are not.

Find the total number of substrings in $�$ that are Schrödinger Smileys.

A substring is obtained by deleting any (possibly zero) number of characters from the beginning and any (possibly zero) number of characters from the end of the string.

Input Format

• The first line of input will contain a single integer $�$, denoting the number of test cases.
• Each test case consists of two lines of input.
  • The first line of each test case contains an integer $�$, the length of the string $�$.
  • The next line contains the string $�$.

Output Format

For each test case, output on a new line, the total number of substrings in $�$ that are Schrödinger Smileys.

Explanation:

Test case $1$: There are $0$ Schrödinger Smiley substrings since there is no right parenthesis present.

Test case $2$: There is $1$ Schrödinger Smiley present that is $�[3,7]=$ :))):.

Test case $3$: The following $2$ substrings are Schrödinger Smileys: