Here is the problem for Valid Parentheses.

1. Understand the problem

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

1. Open brackets are closed by the same type of brackets.

2. Open brackets are closed in the correct order.

2. Clarify requirements

• Only contains ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’, ‘]’.

• Empty string “” → valid.

• Can there be other characters? → No.

• Is “)(“ valid? → No, order matters.

• Expected time/space complexity? → O(n) time, O(n) space is typical.

3. Work through examples

4. Brainstorm 2-3 solutions

4.1. Naive solution

• Remove matched parentheses repeatedly (“()”, “[]”, “{}”). If the string becomes empty → valid.

• 📌 Example:

s = "([{}])"
→ "([{}])" → remove "{}" → "([])" → remove "()" → "[]" → remove "[]" → "" ✔

• Time complexity: O(N^2).

• Space complexity (extra): O(1).

4.2. Stack

• Use a stack to store opening brackets. When encountering a closing bracket, check if it matches the latest opening one.

• Time complexity: O(N).

• Space complexity (extra): O(N).

5. Implement solutions

5.1. Naive solution - O(N^2)

class Solution:
    def isValid(self, s: str) -> bool:
        while '()' in s or '{}' in s or '[]' in s:
            s = s.replace('()', '')
            s = s.replace('{}', '')
            s = s.replace('[]', '')
        return s == ''

• Time complexity: O(N^2).

• Space complexity (extra): O(1).

5.2. Stack solution - O(N)

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        closeToOpen = { ")" : "(", "]" : "[", "}" : "{" }

        for c in s:
            if c in closeToOpen:
                if stack and stack[-1] == closeToOpen[c]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(c)

        return True if not stack else False

6. Dry run testcases