Problem title
Difficulty
Avg time to solve

Find power of a number
Easy
--
Merge K Sorted Arrays
Moderate
15 mins
Topological Sort
Moderate
30 mins
Next Smaller Element
Moderate
25 mins
Cycle Detection in a Singly Linked List
Moderate
15 mins
Valid String
Moderate
18 mins
Max Game
Easy
25 mins
Matrix Median
Moderate
15 mins
Redundant Brackets
Easy
15 mins
Tree Traversals
Easy
15 mins
29

Valid String

Difficulty: MEDIUM
Avg. time to solve
18 min
Success Rate
85%

Problem Statement

You have been given a string 'S' containing only three types of characters, i.e. '(', ')' and '*'.

A Valid String is defined as follows:

1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
5. An empty string is also valid.

Your task is to find out whether the given string is a Valid String or not.

Input Format:
The first line of input contains an integer 'T' representing the number of test cases or queries to run. Then the test case follows.

The only line of each test case contains a string 'S'.
Output Format:
For each test case print 'Yes' if the string 'S' is a valid string otherwise print 'No' otherwise.

The output of each test case will be printed in a separate line.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function. 
Constraints:
1 <= T <= 100
1 <= N <= 5000

Where 'N' is the length of the string 'S'.

Time Limit: 1 sec
Sample Input 1:
3    
*())
(*)
())*
Sample Output 1:
Yes
Yes
No
Explanation of Sample 1:
In the first test case, we can replace '*' with '(' so that the string becomes "(())"

In the second test case, we can replace '*' with an empty string so that the string becomes "()"

In the third test case, there is no way to make the string a valid string.
Sample Input 2:
1
((***
Sample Output 2:
Yes
Reset Code
Full screen
copy-code
Console