Coding

Valid Paranthesis Checker

Asked at

Amazon

Fidelity

PhonePePCPop Club

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Find the validity of an input string s that only contains the letters '(', ')' and '*'.

A string entered is legitimate if

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Input : s = (*)) Output : true Explanation : The * can be replaced by an opening '(' bracket. The string after replacing the * mark is "(())" and is a valid string.

Input : s = *(() Output : false Explanation : The * replaced with any bracket does not form a valid string.

Input : s = (**()))

1 <= s.length <= 104
s consist of only '(', ')', '*'.

cpp

class Solution {  
public:
    bool isValid(string s) {
        //your code goes here
    }
};

java

class Solution {
    public boolean isValid(String s) {
        //your code goes here
    }
}

python

class Solution(object):
    def isValid(self, s):
        #your code goes here

javascript

class Solution {
    isValid(s) {
        //your code goes here
    }
}

csharp

public class Solution
{
    public bool IsValid(string s)
    {
        //your code goes here
    }
}

func IsValid(input string) bool {

}

Stuck? Show a way to structure it+

01Track the minimum and maximum possible unmatched-open counts after each prefix.
02Update both bounds for open, close, and wildcard characters.
03Reject when even the maximum becomes negative; clamp the minimum to zero.
04Accept only when the final minimum is zero.

Reference answer

Maintain a range [low, high] of possible unmatched '(' counts after each prefix. For '(', increment both. For ')', decrement both. For '*', the wildcard may act as ')', empty, or '(', so decrement low and increment high. If high becomes negative, every interpretation has too many closing parentheses, so return false. Clamp low to zero because unmatched-open count cannot be negative; a wildcard can be interpreted as empty instead. After the scan, the string is valid exactly when low == 0, meaning some assignment closes every open parenthesis. This greedy range represents all relevant wildcard choices without branching, yielding O(n) time and O(1) space. Merely checking total counts is insufficient because prefix order matters: a close cannot be matched by a later open.

Then expect these follow-ups

How would you construct one valid wildcard assignment?
Tests: reconstruction
Why is clamping low to zero safe?
Tests: greedy proof

Hiring now

PhonePe has 114 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer, Backend (3-5 years)
Pune, Maharashtra, India
Software Engineer , Backend (5-7 years)
Pune, Maharashtra, India
Software Engineer, App-Android
Bengaluru, Karnataka, India

Or practice this question first

Next question