Problem Statement

Given a string s containing just 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.

Additional information

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

Example 1:

Input: s = "()"

Output: true

Example 2:

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

Output: true

Example 3:

Input: s = "(]"

Output: false

String Replacement (Naive)

Intuition
A valid string of parentheses must contain at least one pair of adjacent matching brackets, like "()", "[]", or "{}". If we remove such a pair, the remaining string must also be valid. We can repeatedly find and remove these pairs. If the string becomes empty, it was valid. If we get stuck with a non-empty string, it is invalid.

Algorithm

1. Calculate length = len(s).
2. While the length of s is greater than 0:

• Replace all occurrences of "()", "[]", and "{}" with an empty string "".
• Calculate the new length.
• If the length hasn't changed (no pairs were removed), return False.

3. Return True (string is empty).

def is_valid(s: str) -> bool:
    while '()' in s or '[]' in s or '{}' in s:
        s = s.replace('()', '').replace('[]', '').replace('{}', '')
    return len(s) == 0

Time & Space Complexity

• Time complexity: O(n^2)

• Reason: In the worst case (e.g., ((((...))))), we iterate n/2 times, and the replace operation takes O(n).

• Space complexity: O(n)

• Reason: Creating new strings during replacement.

Stack (Optimal)

Intuition
This problem requires processing characters in a "Last In, First Out" manner. The most recent opening bracket must be the first one to be closed. This is the perfect use case for a Stack.

We traverse the string. When we see an opening bracket, we push it onto the stack. When we see a closing bracket, we check the top of the stack. If the top matches the correct opening bracket, we pop it (they cancel out). If it doesn't match or the stack is empty, the string is invalid.

Algorithm

1. Initialize an empty stack stack.
2. Create a mapping close_to_open for closing brackets: ) -> (, ] -> [, } -> {.
3. Iterate through each character c in s.
4. If c is a closing bracket (key in map):

• If the stack is not empty and the top of the stack matches close_to_open[c], pop the stack.
• Otherwise, return False (mismatch or empty stack).

5. If c is an opening bracket, push it onto the stack.
6. After the loop, return True if the stack is empty, otherwise False.

def is_valid(s: str) -> bool:
    stack = []
    close_to_open = {")": "(", "]": "[", "}": "{"}

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

    return True if not stack else False

Time & Space Complexity

• Time complexity: O(n)

• Reason: We traverse the string once, pushing and popping each character at most once.

• Space complexity: O(n)

• Reason: In the worst case (e.g., (((((), the stack grows to size n.