Problem Definition

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

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

Examples

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

Algorithmic Approach

The structure of nested parentheses suggests a Last-In-First-Out (LIFO) processing order. When encountering an opening bracket, it is stored until a corresponding closing bracket appears. The most recently opened bracket must be the first one closed. This bheavior aligns perfectly with a stack data structure.

1. Initialize an empty stack.
2. Iterate through each chraacter in the string.
3. If the character is an opening bracket, push the corresponding expected closing bracket onto the stack.
4. If the character is a closing bracket, check if the stack is empty or if the top of the stack does not match the current character. If either condition is true, the string is invalid.
5. If the character matches the top of the stack, pop the element.
6. After ietrating through the entire string, the stack must be empty for the string to be valid.

Java Implementation

import java.util.Deque;
import java.util.ArrayDeque;

class Solution {
    public boolean checkValidity(String input) {
        if (input == null || input.isEmpty()) {
            return true;
        }
        
        // Odd length strings cannot be valid
        if ((input.length() & 1) == 1) {
            return false;
        }

        Deque<Character> bracketStack = new ArrayDeque<>();
        
        for (char currentChar : input.toCharArray()) {
            if (currentChar == '(') {
                bracketStack.push(')');
            } else if (currentChar == '[') {
                bracketStack.push(']');
            } else if (currentChar == '{') {
                bracketStack.push('}');
            } else {
                if (bracketStack.isEmpty() || bracketStack.pop() != currentChar) {
                    return false;
                }
            }
        }
        
        return bracketStack.isEmpty();
    }
}