Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Valid String

Moderate
0/80
Average time to solve is 18m
58 upvotes
Asked in companies
SalesforcePaytm (One97 Communications Limited)Visa

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Full screen
Console