LeetCode 2116: Check if a Parentheses String Can Be Valid Solution

Master LeetCode problem 2116 (Check if a Parentheses String Can Be Valid), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

2116. Check if a Parentheses String Can Be Valid

Medium

String Stack Greedy

Problem Explanation

Explanation:

To solve this problem, we can use a stack to keep track of the parentheses. We iterate through the input string s, and for each character:

If it is a '(' or ')', we check if we can change it based on the corresponding locked position.
If it is a '(', we push its index to the stack.
If it is a ')', we try to match it with the top element of the stack. If there is a match, we pop the stack; otherwise, we check if we can change the current ')' to '(' based on the locked positions.

After iterating through the entire string, we check if the stack is empty. If it is empty, it means all parentheses are matched and valid, so we return true; otherwise, we return false.

Time Complexity:

The time complexity of this solution is O(n), where n is the length of the input string s.

Space Complexity:

The space complexity is also O(n) due to the stack used to keep track of the parentheses.

Solution Code

class Solution {
    public boolean checkValidString(String s, String locked) {
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else if (s.charAt(i) == ')') {
                if (!stack.isEmpty() && s.charAt(stack.peek()) == '(') {
                    stack.pop();
                } else {
                    boolean canChange = false;
                    for (int j = i - 1; j >= 0; j--) {
                        if (s.charAt(j) == '(' && locked.charAt(j) == '0') {
                            canChange = true;
                            break;
                        }
                    }
                    if (!canChange) return false;
                }
            }
        }
        
        while (!stack.isEmpty()) {
            int idx = stack.pop();
            if (locked.charAt(idx) == '0') {
                boolean canChange = false;
                for (int j = idx + 1; j < s.length(); j++) {
                    if (s.charAt(j) == ')' && locked.charAt(j) == '0') {
                        canChange = true;
                        break;
                    }
                }
                if (!canChange) return false;
            } else {
                return false;
            }
        }
        
        return true;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 2116 (Check if a Parentheses String Can Be Valid)?

This page provides optimized solutions for LeetCode problem 2116 (Check if a Parentheses String Can Be Valid) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 2116 (Check if a Parentheses String Can Be Valid)?

The time complexity for LeetCode 2116 (Check if a Parentheses String Can Be Valid) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 2116 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2116 in Java, C++, or Python.

Back to LeetCode Solutions