Valid Parentheses in O(n) Time Complexity using Java

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.

Example 1:

Input: s = "()"
Output: true

Example 2:

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

Example 3:

Input: s = "(]"
Output: false

Example 4:

Input: s = "([)]"
Output: false

Example 5:

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

Constraints:

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

Understanding the Problem

The core challenge of this problem is to ensure that every opening bracket has a corresponding closing bracket and that they are correctly nested. This problem is significant in various applications such as parsing expressions in compilers, validating mathematical expressions, and ensuring the correctness of nested structures in programming languages.

Potential pitfalls include mismatched brackets, incorrect nesting, and unbalanced brackets.

Approach

To solve this problem, we can use a stack data structure. The stack helps us keep track of the opening brackets encountered, and we can match them with the corresponding closing brackets as we traverse the string.

Naive Solution

A naive solution might involve checking each pair of brackets, but this would be inefficient and complex to implement. This approach is not optimal due to its high time complexity.

Optimized Solution

The optimized solution involves using a stack to keep track of the opening brackets. As we traverse the string, we push each opening bracket onto the stack. For each closing bracket, we check if it matches the top of the stack. If it does, we pop the stack; otherwise, the string is invalid.

Algorithm

Initialize an empty stack.
Traverse each character in the string.
If the character is an opening bracket, push it onto the stack.
If the character is a closing bracket, check if the stack is empty or if the top of the stack does not match the corresponding opening bracket. If either condition is true, return false.
If the stack is not empty at the end of the traversal, return false.
Otherwise, return true.

Code Implementation

import java.util.Stack;

public class ValidParentheses {
    public boolean isValid(String s) {
        // Initialize a stack to keep track of opening brackets
        Stack<Character> stack = new Stack<>();
        
        // Traverse each character in the string
        for (char c : s.toCharArray()) {
            // If the character is an opening bracket, push it onto the stack
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                // If the stack is empty or the top of the stack does not match the closing bracket, return false
                if (stack.isEmpty() || !isMatchingPair(stack.pop(), c)) {
                    return false;
                }
            }
        }
        
        // If the stack is not empty, return false
        return stack.isEmpty();
    }
    
    // Helper method to check if the characters are matching pairs
    private boolean isMatchingPair(char open, char close) {
        return (open == '(' && close == ')') ||
               (open == '{' && close == '}') ||
               (open == '[' && close == ']');
    }

    public static void main(String[] args) {
        ValidParentheses vp = new ValidParentheses();
        System.out.println(vp.isValid("()")); // true
        System.out.println(vp.isValid("()[]{}")); // true
        System.out.println(vp.isValid("(]")); // false
        System.out.println(vp.isValid("([)]")); // false
        System.out.println(vp.isValid("{[]}")); // true
    }
}

Complexity Analysis

The time complexity of this solution is O(n) because we traverse the string once. The space complexity is also O(n) due to the stack used to store the opening brackets.

Edge Cases

Potential edge cases include:

Empty string: Should return true.
Single type of bracket: "((()))" should return true, "((())" should return false.
Mixed types of brackets: "{[()]}" should return true, "{[(])}" should return false.

Testing

To test the solution comprehensively, consider the following test cases:

Simple balanced brackets: "()", "[]", "{}"
Mixed balanced brackets: "()[]{}", "{[()]}"
Unbalanced brackets: "(", ")", "([)]", "((())"
Edge cases: "", "(((((((())))))))"

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to:

Understand the problem requirements and constraints.
Break down the problem into smaller, manageable parts.
Consider using data structures like stacks or queues to manage nested structures.
Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed the problem of validating parentheses using a stack-based approach. We explored the problem definition, potential pitfalls, and provided a detailed algorithm and code implementation in Java. Understanding and solving such problems is crucial for developing strong problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources: