Valid Parenthesis String
Valid Parenthesis String is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Stack Patterns pattern, in the Valid Parentheses Matching subpattern.
Problem statement
Given a string s, determine whether it can represent a correctly balanced sequence of parentheses. The string contains opening parentheses (, closing parentheses ), and wildcard characters .
Each may be interpreted as a single (, a single ), or an empty character. All non-wildcard characters retain their original meaning, and each wildcard receives exactly one of these interpretations.
Return true if some interpretation of every produces a valid parenthesis sequence, and return false otherwise. A valid sequence has matching pairs in the proper order, with no closing parenthesis appearing before its matching opening parenthesis.
Example 1:
Input: s = "(()" Output: true Explanation: Interpret as ), producing (()), which is balanced.
Example 2:
Input: s = "())" Output: false Explanation: The first three characters already leave one unmatched closing parenthesis, and the final wildcard cannot repair that ordering.
Example 3:
Input: s = "" Output: true Explanation: For instance, interpret the three wildcards as (, ), and an empty character to obtain ().
Constraints:
- 1 <= s.length <= 10^5 - Each character in s is (, ), or . - Each represents at most one character in the interpreted sequence. - The input string is provided as a JSON string.
Topics and companies
Topics: Greedy, Stack, String.
How to practise Valid Parenthesis String on Thita.ai
Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n), where n is the length of s. time and O(1) space.
Open Valid Parenthesis String in the code editor, or read the Valid Parenthesis String editorial for a worked solution with its approach and complexity analysis.
Where Valid Parenthesis String sits in the DSA pattern sheet
- Stack Patterns pattern guide
- Valid Parentheses Matching subpattern
- The full DSA patterns sheet
- All coding practice problems
Problems related to Valid Parenthesis String
Other problems that use the same Valid Parentheses Matching and Stack Patterns techniques:
- Longest Valid Parentheses — Hard, same subpattern
- Minimum Add to Make Parentheses Valid — Medium, same subpattern
- Minimum Number of Swaps to Make the String Balanced — Medium, same subpattern
- Minimum Remove to Make Valid Parentheses — Medium, same subpattern
- Valid Parentheses — Easy, same subpattern
- Asteroid Collision — Medium, same pattern