CODU considers string as a good string if it is balanced with stars. A string is considered as balanced with stars if string contains
balanced brackets and between every pair of bracket i.e. between opening and closing brackets, there are at least 2 stars(*) present.
CODU knows how to check whether a string is balanced or not but this time he needs to keep a track of stars too. He decided to
write a program to check whether a string is good or not. But CODU is not as good in programming as you are, so he decided to
take help from you. Will you help him for this task? You need to print Yes and number of balanced pair if string satisfies following
conditions(string is good if it satisfies following 2 conditions):
- The string is balanced with respect to all brackets.
- Between every pair of bracket there is at least two stars.
However if string doesn’t satisfies above conditions then print No and number of balanced pair in string as an output.
Example 1
Input
{({[]})}
Output
Yes 4
Explanation
String has balanced brackets and also satisfies 2nd condition. So the output is Yes with count of balanced pair which is 4.
Example 2
Input
}xasd[]sda231
Output
No 1
Explanation
In this case string is not balanced. So the output is No with the count of balanced pair as 1.
Please add link to question so that it will be easier for other people to solve it and explain/help you.
Not just that, but also so we know they aren’t cheating on something
No I am not cheating 
, it is a last year question of codevita prequalifer zonal round.
For anyone else interested, here is the link - it’s legit (but would have been nice if you had initially provided it)
I think the question is vague. For example, is this: {{**}} a balanced string? Between both pairs, there are two stars, but it’s the same two stars for both pairs. I’m going to assume that is the case because that’s how the wording seems to convey it, but the samples don’t help in this regard.
Now, notice that each type of bracket is independent. So you can store a stack for each type of bracket that contains an entry for each left bracket, as well as the number of stars seen since the position of the left bracket.
When you encounter a left bracket, push a new entry onto the corresponding stack, with a star count of 0. When you encounter a right bracket, pop the corresponding stack, and add the number of stars from the popped element to the new top of the stack (or not, if it becomes empty). When you encounter a star, add one to the counts of each stack’s top (or not, if they’re empty).
If you ever have to pop from an empty stack, the string is invalid. If a popped element’s star count is ever less than 2, the string is invalid. If all of the stacks are not empty when you reach the end of the string, the string is invalid. Otherwise it’s valid.
Notice that this is convenient because if my above assumption about the statement is wrong, the only necessary modification is not adding the number of stars from the popped element to the new top of the stack when you’re on a right bracket.
1 Like
what is ans for {(**} and {**)} any idea