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 )
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
Hint

Try each of the three possibilities for every asterisk in the string.

Approaches (3)
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. In the end, we can linearly check each possible string. If any of the possible string is a valid string, we print ‘Yes’, otherwise ‘No’.

Time Complexity

O(N * 3^N),  where ‘N’ is the length of the string.

 

In the worst-case scenario, we can have all the characters in the string as asterisks. So, we will be trying 3^N possible strings and check all of them in linear time for validity. Hence the overall complexity will be O(N* 3^N)

Space Complexity

O(N), where ‘N’ is the length of the string.

 

In the worst-case scenario, our temporary string can have a length of at most the length of the given string. Also, our recursion stack can grow at most the length of the string. Hence the overall time complexity is O(N).

Code Solution
(100% EXP penalty)
Valid String
All tags
Sort by
Search icon

Interview problems

2 Pointer || Easy One || C++ || 100%

#include <bits/stdc++.h>

bool checkValidString(string &s) {

  // Write your code here.

  int low = 0;

  int high = 0;

 

  for (char ch : s){

      if(ch=='('){

          low++;

          high++;

      }else if(ch==')'){

          if(low>0) low--;

          high--;

      }else{

          if(low>0) low--;

          high++;

      }

 

      if(high<0){

          return false;

      }

  }

  return low==0;

}

54 views
0 replies
0 upvotes

Interview problems

easy c++ code || upvote if this helped

#include <bits/stdc++.h> 

bool checkValidString(string &s){

    // Write your code here.

    stack<int>x;

    stack<int>y;

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

    {

        char ch = s[i];

        if(ch=='(')

        {

            x.push(i);

        }

        else if(ch=='*')

        {

            y.push(i);

        }

        else

        {

            if(!x.empty())

            {

                x.pop();

            }

            else if(!y.empty())

            {

                y.pop();

            }

            else

            {

                return false;

            }

        }

    }

    while(!x.empty() && !y.empty())

    {

        if(x.top()>y.top())

        {

            return false;

        }

        x.pop();

        y.pop();

    }

    return x.empty();

}

101 views
0 replies
1 upvote

Interview problems

Simple solution using C++ (Stacks)

We are using two stacks here 

i) to store the paranthesis  (x)  ii) to store the asterik (y) 

-→ Whenever we encounter a open paranthesis or an asterick we push their indices to respective stacks

 -→ If we encounter a closed paranthesis first we'll check if the paranthesis stack is empty or not 

if not empty we'll pop the top element of stack . if not we'll check the asterik stack and do the same with it  

-→ if both are empty and there is a closing paranthesis to match with we can return false 

-→ What if there are no closing paranthesis in the given string  

Ex : “( ( (  * * *” 

-→ we push the indices into the stack and there are not empty 

-→ that means even we iterate over the entire string , the stacks are not empty 

-→ then we'll compare the indices lying on top of each stack,

if open paranthesis index is greater than closing one (matching with asterick  here ) then we return false 

-→ else we pop both stack's top

 -→finally if the paranthesis stack is empty means our ans is true 

else its false

 

 #include<bits/stdc++.h>

bool checkValidString(string &s) {

    stack<int> x;

    stack<int> y;

    for(int i=0;i<s.size();i++)

    {

        char c=s[i];

        if(c=='(')

        {

            x.push(i);

        }

        else if(c=='*')

        {

            y.push(i);

        }

        else

        {

            if(!x.empty())

            {

                x.pop();

            }

            else if(!y.empty())

            {

                y.pop();

            }

            else

              return false;

        }

    }

    while(!x.empty() && !y.empty())

    {

        if(x.top() > y.top())

            return false;

        x.pop();y.pop();

    }

    return x.empty();

}

174 views
0 replies
2 upvotes

Interview problems

cpp optimal solution

#include <bits/stdc++.h> 

bool checkValidString(string &s){

 

    if(s.length()==0)return true;

    

    int balance=0;

 

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

        if(s[i]==')')balance--;

        else balance++;

 

        if(balance<0)return false;

    }

 

    if(balance==0)return true;

 

    balance=0;

 

    for(int i=s.length()-1;i>=0;i--){

        if(s[i]=='(')balance--;

        else balance++;

 

        if(balance<0)return false;

    }

 

    return true;

}

214 views
0 replies
0 upvotes

Interview problems

Explained Why We are taking * as left and right

import java.util.* ;
import java.io.*; 
public class Solution {
	public static boolean checkValidString(String s) {
        // Write your code here.
                int leftmin = 0;
                int leftmax = 0;
                for(char c : s.toCharArray()){
                        if(c=='('){
                                leftmin++;
                                leftmax++;
                        }
                        else if(c==')'){
                                leftmax--;
                                leftmin--;
                        }
                        else{
                                leftmin--;// when * is right 
                                leftmax++;// when * is left
                        }
                        leftmin = Math.max(leftmin,0); 
                        // to maintain if right is equal then the left min will be zero and 
                        // * will extra add ) and the val is less than 0 
                        // but in the case of not valid ) then left is extra which we will try to fulfill with *
                        // although not fulfilled then it will give more than 0 and not balanced;
                        if(leftmax<0) return false;
                }
                return leftmin == 0;
        }		
}

java

112 views
0 replies
0 upvotes

Interview problems

JAVA solution using stack|| 100% correct

import java.util.* ;
import java.io.*; 
public class Solution {
	public static boolean checkValidString(String s) {
        // Write your code here.	
		Stack<Integer> openBracket = new Stack<>();// to store the open bracket
		Stack<Integer> stars = new Stack<>();//to store stars('*')

		for(int i=0; i<s.length(); i++){
			if(s.charAt(i)== '*'){//CASE I
				stars.push(i);
			}
			else if(s.charAt(i)== '('){//CASE II
				openBracket.push(i);
			}
			else{//CASE III
				if(openBracket.size()!=0){
					openBracket.pop();
				}
				else if(stars.size()!=0){
					stars.pop();
				}
				else{
					return false;
				}
			}
		}

		while(openBracket.size()!=0){
			if(stars.size()==0){
				return false;
			}else if(openBracket.peek() < stars.peek()){
				openBracket.pop();
				stars.pop();
			}else{
				return false;
			}
		}

		return true;
	}	
}

java

96 views
0 replies
0 upvotes

Interview problems

Valid String Optimal soln C++

#include <bits/stdc++.h> 

bool checkValidString(string &s){

    // Write your code here.

    int open_count = 0;

    int close_count = 0;

    if(s[0] == ')'){

        return false;

    }

    for(int i=0;i<s.size();i++){

        if(s[i] == '*' || s[i] == '('){

            open_count++;

        }

        else{

            close_count++;

        }

                if (close_count > open_count) {

                        return false;

                }

        }

                open_count=0;

        close_count = 0;

        for(int i = s.size()-1;i>=0;i--){

            if(s[i] == '*' || s[i] == ')'){

                close_count++;

            }

            else{

                open_count++;

            }

            if(open_count > close_count){

                return false;

            }

        }

         

 

         

    

    return true;

}

197 views
0 replies
2 upvotes

Interview problems

JAVA best sol:)

import java.util.*;

import java.io.*;

public class Solution {

        public static boolean checkValidString(String s) {

        // Write your code here.

                int low = 0, high = 0;

                for (char c : s.toCharArray()) {

                        low += (c == '(') ? 1 : -1;

                        high += (c != ')') ? 1 : -1;

                        if (high < 0) break;

                        low = Math.max(low, 0);

                }

                return low == 0;

        }

}

 

java

137 views
0 replies
1 upvote

Interview problems

How to edit this code to pass the last test case

MyCode got 8/9 and my code didn't get a good answer at “*))”

 

#include <bits/stdc++.h> 
bool checkValidString(string &s){
	int noProblem=0,b=1;
	vector<char> arr;
	for(int i=0; i<s.length(); i++) {
		//if(s[i] == '(' && !b) b=1;
		if(s[i] == '(') arr.push_back(')');
		else if(s[i] == ')') {
			if(arr.size()) arr.pop_back(); else if(!noProblem) return false; else noProblem+=(s[i+1] == ')' ? 0 : 1);
		} else {
			if(arr.size()) arr.pop_back(); else b=0; // else arr.push_back(')');
			noProblem++;
		}
	}
	return !arr.size();// && s.find(")*))") != string::npos;
}
110 views
0 replies
0 upvotes

Interview problems

C++ Solution O(N)

#include <bits/stdc++.h> 

using namespace std;

bool checkValidString(string &s)

{

    stack<int> open,star;

        int len = s.length();

        

        for(int i=0;s[i]!='\0';++i)

        {

            if(s[i]=='(')

                open.push(i);

            else if(s[i]=='*')

                star.push(i);

            else

            {

                if(!open.empty())

                    open.pop();

                else if(!star.empty())

                    star.pop();

                else

                    return false;

            }

        }

        

        //Now process leftover opening brackets

        while(!open.empty())

        {

            if(star.empty())

                return false;

            else if(open.top() < star.top())

            {

                open.pop();

                star.pop();

            }

            else    //CASE: open.top() > star.top()

                return false;

        }

        return true;

    

}

473 views
0 replies
2 upvotes
Full screen
Console