Given a string s of '(' , ')' and lowercase English characters.

Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

• It is the empty string, contains only lowercase characters, or

• It can be written as AB (A concatenated with B), where A and B are valid strings, or

• It can be written as (A), where A is a valid string.

LeetCode Problem - 1249

class Solution {
    // Method to remove minimum number of parentheses to make the input string valid
    public String minRemoveToMakeValid(String s) {
        // StringBuilder to store the processed string
        StringBuilder sb = new StringBuilder();
        // Counter to keep track of open parentheses
        int openParentheses = 0;

        // Iterating through each character in the input string
        for (char c : s.toCharArray()) {
            // If the character is an opening parenthesis, increment the openParentheses counter
            if (c == '(')
                openParentheses++;
            // If the character is a closing parenthesis
            else if (c == ')') {
                // If there are no corresponding opening parentheses left, skip this closing parenthesis
                if (openParentheses == 0)
                    continue;
                // Otherwise, decrement the openParentheses counter to match this closing parenthesis
                openParentheses--;
            }
            // Append the character to the StringBuilder
            sb.append(c);
        }

        // StringBuilder to store the final result
        StringBuilder result = new StringBuilder();
        // Iterating through the characters in the processed StringBuilder in reverse order
        for (int i = sb.length() - 1; i >= 0; i--) {
            // If the character is an opening parenthesis and there are extra opening parentheses remaining, skip it
            if (sb.charAt(i) == '(' && openParentheses-- > 0)
                continue;
            // Otherwise, append the character to the result StringBuilder
            result.append(sb.charAt(i));
        }

        // Reverse the result StringBuilder and convert it to a string before returning
        return result.reverse().toString();
    }
}