Valid String

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
CodingNinjas
author
2y
Brute Force

We can try each of the three possibilities for every asterisk in the string with the help of recursion.

We will use a temporary string which will keep track of our current possible string....read more

CodingNinjas
author
2y
Dynamic Programming

The problem can be divided into smaller sub-problems and hence, we can use a dynamic programming approach which will be similar to the Matrix Chain Multiplication’s dynamic programm...read more

CodingNinjas
author
2y
Two pointers

Let’s first focus on the problem when there are no asterisks. For this problem, we can just use a variable to count the unmatched ‘(‘. Clearly, we don't want the value of this variable to ...read more

Add answer anonymously...
SimplifyVMS Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
qr-code
Helping over 1 Crore job seekers every month in choosing their right fit company
65 L+

Reviews

4 L+

Interviews

4 Cr+

Salaries

1 Cr+

Users/Month

Contribute to help millions
Get AmbitionBox app

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2024 Info Edge (India) Ltd.

Follow us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter