Valid strings

help
1

Valid Strings

Arnab loves brackets and any valid sequence of brackets. On his birthday, he expected a valid sequence of brackets from his friends. He is upset because some of his friends deliberately gifted him an invalid sequence. Now, Arnab decided to fix the sequence himself by moving only one of the brackets in the sequence.

A bracket sequence ( S ) is valid only if: 1. S is empty 2. S is equal to “( t )”, where t is a valid sequence 3. S is equal to “( t1 t2 )” ie. concatenation of t1 and t2 , where t1 and t2 are valid sequences.

Arnab, being a lazy person wants you to check if the sequence can be made valid by moving just one bracket (if required).

Input format

First-line contains an integer TT where TT is the number of test cases. The next TT lines contain a String SS denoting the sequence.

Output format

For each test case on a new line, print Yes or No depending on whether it is possible or not to convert the string into a valid string.

Constraints:

1<=T<=701<=T<=70 1<=|S|<=1051<=|S|<=105 , where |S||S| denotes the length of the string.

Time Limit

11 second

Example

Input

1 )(

Output

Yes

Sample test case explanation

we have the sequence )( so by moving the first bracket to the last we get () so it becomes a valid string.

2

can the strings be already valid
will that be a yes

3
5

The below code is taken from geeksforgeeks by sanjeev2552. The code got accepted in Prepbytes.
The logic lies in adding another ‘()’ that will check for utmost one change.

import java.util.;
import java.io.;

public class Main {
public static void main(String args[]) throws IOException {
Scanner sc = new Scanner(System.in);
short T = sc.nextShort();
while(T–>0) {
String s = sc.next();
int len=s.length();
if(canBeBalanced(s,len))
System.out.println(“Yes”);
else
System.out.println(“No”);
}
}
static boolean canBeBalanced(String s, int n)
{

    // Odd length string can
    // never be balanced
    if (n % 2 == 1)
        return false;

    // Add '(' in the beginning and ')'
    // in the end of the string
    String k = "(";
    k += s + ")";
    Vector<String> d = new Vector<>();

    for (int i = 0; i < k.length(); i++)
    {

        // If its an opening bracket then
        // append it to the temp string
        if (k.charAt(i) == '(')
            d.add("(");

        // If its a closing bracket
        else
        {

            // There was an opening bracket
            // to match it with
            if (d.size() != 0)
                d.remove(d.size() - 1);

            // No opening bracket to
            // match it with
            else
                return false;
        }
    }

    // Sequence is balanced
    if (d.isEmpty())
        return true;
    return false;
}

}

6

this solution also worked :
for _ in range(int(input())):
s = input()
c = 0
flag = 0
for i in s:
if i == ‘(’:
c+=1
else:
c-=1
if c < -1:
flag = 1
break
if flag == 1 or c!=0:
print(‘No’)
else:
print(‘Yes’)