Minimum Add to Make Parentheses Valid
As a Systems Engineer at Tata Consultancy Services, I deliver exceptional software products for mobile and web platforms, using agile methodologies and robust quality maintenance. I am experienced in performance testing, automation testing, API testing, and manual testing, with various tools and technologies such as Jmeter, Azure LoadTest, Selenium, Java, OOPS, Maven, TestNG, and Postman.
I have successfully developed and executed detailed test plans, test cases, and scripts for Android and web applications, ensuring high-quality standards and user satisfaction. I have also demonstrated my proficiency in manual REST API testing with Postman, as well as in end-to-end performance and automation testing using Jmeter and selenium with Java, TestNG and Maven. Additionally, I have utilized Azure DevOps for bug tracking and issue management.
A parentheses string is valid if and only if:
It is the empty string,
It can be written as
AB(Aconcatenated withB), whereAandBare valid strings, orIt can be written as
(A), whereAis a valid string.
You are given a parentheses string s. In one move, you can insert a parenthesis at any position of the string.
- For example, if
s = "()))", you can insert an opening parenthesis to be"(()))"or a closing parenthesis to be"())))".
Return the minimum number of moves required to make s valid.
LeetCode Problem - 921
class Solution {
public int minAddToMakeValid(String s) {
Stack<Character> stack = new Stack<>(); // Stack to track unmatched parentheses
// Iterate through each character in the string
for (char ch : s.toCharArray()) {
if (stack.isEmpty()) { // If stack is empty, push the current character
stack.push(ch);
}
// If we find a closing bracket ')' and the top of the stack is an open bracket '('
else if (stack.peek() == '(' && ch == ')') {
stack.pop(); // Valid pair, so we remove the open bracket from the stack
}
// Otherwise, push the current character (either '(' or unmatched ')')
else {
stack.push(ch);
}
}
// The remaining size of the stack represents the number of unmatched parentheses
return stack.size();
}
}
