Solve the Easy-level Valid Parentheses coding interview problem online in Python & JavaScript. Run your code against real test cases in the browser and study worked examples. It covers strings and stack. Read the step-by-step solution and complexity analysis. Java starter code is also included for reference (no in-browser JVM yet, so it can't be run here).

Valid Parentheses – Solve Online in Python & JavaScript

## Problem Description

Given a string 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.

Note that an empty string is also considered valid.

### Example

```python
assert is_valid("()") == True
assert is_valid("()[]{}") == True
assert is_valid("(]") == False
```

- Every opening bracket must be closed by the same bracket type.
- Brackets must close in the reverse order they were opened.
- That reverse-order requirement is the key clue to use a stack.

Understand Valid Nesting

- Counting open and closed brackets can catch some invalid strings.
- It fails for inputs like `(]`, where the counts look balanced but the types do not match.
- We need to remember the exact most recent unmatched opening bracket.

Why Counting Is Not Enough

- Push opening brackets onto a stack.
- When a closing bracket appears, it must match the bracket at the top of the stack.
- If the stack is empty or the type is wrong, the string is invalid immediately.

Use a Stack for Open Brackets

- Store closing-to-opening bracket pairs in a dictionary.
- For each closing bracket, pop the stack and compare it with the expected opener.
- At the end, the stack must be empty for all brackets to be matched.

Handle Closing Brackets

- The final algorithm scans the string once and uses the stack to enforce correct order.
- Time complexity is O(n), where `n` is the length of the string.
- Space complexity is O(n) in the worst case when all characters are opening brackets.