Ace Your Next Coding Interview: Solving the Valid Parentheses Question

7 min readJan 28, 2023

Hello everyone, I am a software developer with 7 years of experience in backend development. Throughout my career, I have had the opportunity to work at some of the top product-based companies in the world. In this blog post, I am excited to share my insights on one of the most common interview questions for software developers, the Valid Parentheses problem.

This is a post in my series “Ace Your Next Coding Interview” posts where I am discussing popular DSA (Data Structures and Algorithm) interview questions. I will be providing various approaches to solving these problems and providing code examples in Java. Whether you are a beginner or an experienced developer, I hope you find this information useful in your journey to becoming a better programmer and ace your next DSA interview.

Valid Parentheses Problem

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

Constraints:

1 <= s.length <= 104
s consists of parentheses only '()[]{}'.

Brute Force Solution

The brute force solution for the Valid Parentheses problem involves checking all possible combinations of parentheses in the input string to see if they are valid. To implement this solution, we can use recursion. We can check all the combinations of the input string by removing one character at a time and recursing on the remaining string. For each combination, we can check if the combination is valid by iterating through the characters and ensuring that all open parentheses have a matching closing parenthesis in the correct order.

Here is an example of the brute force solution implemented in Java:

class Solution {
    public boolean isValid(String s) {
        // Base case: if the input string is empty, it is considered valid
        if (s.length() == 0) return true;
        // Iterate through all possible combinations of the input string by removing one character at a time
        for (int i = 0; i < s.length(); i++) {
            // Recurse on the remaining string after removing the current character
            String subString = s.substring(0, i) + s.substring(i + 1);
            if (isValid(subString)) {
                // Iterate through the characters of the current combination
                int count = 0;
                for (int j = 0; j < subString.length(); j++) {
                    char c = subString.charAt(j);
                    if (c == '(' || c == '{' || c == '[') {
                        count++;
                    } else if (c == ')' || c == '}' || c == ']') {
                        count--;
                    }
                    // If at any point, there are more closing parentheses than opening, the combination is not valid
                    if (count < 0) return false;
                }
                // If the combination is valid and all parentheses are matching and in the correct order, return true
                if (count == 0) return true;
            }
        }
        // If no combination is valid, return false
        return false;
    }
}

The time complexity of the brute force solution is O(n!*n) where n is the size of the input string. This is because we are using recursion and generating all possible combinations of the input string, which is factorial time complexity, and also iterating through each of the combination with n to check if it is valid. The space complexity of the brute force solution is O(n) as we are using recursion to generate all possible combinations of the input string.

It’s important to note that the brute force solution is not efficient for large inputs and it is not recommended for use in real-world applications where performance is a concern.

Optimized Stack Solution

The stack solution is a more efficient approach for solving the Valid Parentheses problem. The idea is to use a stack to keep track of the open parentheses as we iterate through the input string. For each character in the input string, we check if it is an open parenthesis. If it is, we push it onto the stack. If it is a closing parenthesis, we check if the top element of the stack is a matching open parenthesis. If it is, we pop the top element from the stack. If it is not a matching open parenthesis, or if the stack is empty, the input string is not valid.

Here is an example of the stack solution implemented in Java:

class Solution {
    public boolean isValid(String s) {
        // Create a stack to keep track of the open parentheses
        Stack<Character> stack = new Stack<>();
        // Iterate through the characters of the input string
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // If the current character is an open parenthesis, push it onto the stack
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
 // If the current character is a closing parenthesis, check if the top element of the stack is a matching open parenthesis
                if (stack.isEmpty()) {
                    // If the stack is empty, the input string is not valid
                    return false;
                } else if (c == ')' && stack.peek() == '(') {
                    // If the current character is a ')' and the top element of the stack is a '(', pop the top element off the stack
                    stack.pop();
                } else if (c == '}' && stack.peek() == '{') {
                    // If the current character is a '}' and the top element of the stack is a '{', pop the top element off the stack
                    stack.pop();
                } else if (c == ']' && stack.peek() == '[') {
                    // If the current character is a ']' and the top element of the stack is a '[', pop the top element off the stack
                    stack.pop();
                } else {
                    // If the current character is not a matching open parenthesis, the input string is not valid
                    return false;
                }
            }
        }
        // If the stack is empty, the input string is valid
        return stack.isEmpty();
    }
}

Stack solution with Config HashMap

To make the solution more extensible & sophisticated, We can create a config map that maps open and closing parentheses to each other. So when next time you want to introduce a new parenthesis pair you can just add it to the config and you won’t need to change your function.

class Solution {
    // Create a config map that maps open and closing parentheses to each other
    private Map<Character, Character> config = new HashMap<Character, Character>() {{
        put('(', ')'); // map '(' to ')'
        put('{', '}'); // map '{' to '}'
        put('[', ']'); // map '[' to ']'
    }};

    public boolean isValid(String s) {
        // Create a stack to keep track of the open parentheses
        Stack<Character> stack = new Stack<>();
        // Iterate through the characters of the input string
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            // If the current character is an open parenthesis, push it onto the stack
            if (config.containsKey(c)) {
                stack.push(c);
            } else {
                // If the current character is a closing parenthesis, check if the top element of the stack is a matching open parenthesis
                if (stack.isEmpty() || c != config.get(stack.pop())) {
                    // If the stack is empty or the current character is not a matching open parenthesis, the input string is not valid
                    return false;
                }
            }
        }
        // If the stack is empty, the input string is valid
        return stack.isEmpty();
    }
}

The time complexity of the stack solution is O(n) where n is the size of the input string. This is because we are iterating through the input string only once and performing constant time operations for each character. The space complexity of the stack solution is also O(n) as we are using a stack to keep track of the open parentheses. Even if we go with the config map, the complexity will stay the same as we have constant number of parenthesis.

Common Mistakes

Not considering the edge cases like an empty string.
Not understanding the time and space complexity requirements.
Not using the correct data structure like using a queue instead of a stack.
Not handling the matching of the parentheses properly.

Conclusion

The Valid Parentheses problem is a classic problem that requires determining whether the input string is valid based on matching and ordering of parentheses. We have discussed the brute force solution, which is not efficient, and the stack solution which is more efficient. It is important to choose the right approach for a given problem and also keep in mind the common mistakes that people make while solving this question in an interview.

I hope you found this post informative and useful. Stay tuned for more DSA interview question blog posts in the series. Follow me for more updates and insights on popular DSA interview questions or engineering mentorship.

To learn more about Ace Your Next Coding Interview series, checkout https://sde-mentor.medium.com/list/ace-your-next-coding-interview-series-a847a9d1e57f

To learn more about mentorship, Checkout my mentorship series here: https://medium.com/@sde-mentor/list/mentorship-series-be62191a4c87