Jobs

Interviews

Discussions

Valid Parentheses

Easy

Roblox

0 views

Topics:

StringsStacks

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.
Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"

Output: true

Example 2:

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

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

Example 5:

Input: s = "([)]"

Output: false

Constraints:

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

Valid Parentheses

Easy

Roblox

0 views

Topics:

StringsStacks

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.
Every close bracket has a corresponding open bracket of the same type.

Example 1:

Input: s = "()"

Output: true

Example 2:

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

Output: true

Example 3:

Input: s = "(]"

Output: false

Example 4:

Input: s = "([])"

Output: true

Example 5:

Input: s = "([)]"

Output: false

Constraints:

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` be empty or null? If so, what should I return?
Are there any characters other than '(', ')', '{', '}', '[', and ']' in the input string? If so, how should I handle them?
Is the length of the string `s` constrained? This could impact space complexity considerations.
If the string is invalid, are there specific error codes or exceptions I should raise, or is returning `false` sufficient?
By 'correct order', do you mean that for every opening bracket, there must be a corresponding closing bracket of the same type appearing later in the string, and nested brackets must also follow this rule?

Brute Force Solution

Approach

The brute force approach to checking if parentheses are valid means we're going to try to remove matching pairs one by one until we either have no parentheses left (valid) or can't remove any more (invalid). It's like peeling layers of an onion until you get to the core.

Here's how the algorithm would work step-by-step:

Look at the entire string of parentheses.
Find a pair of adjacent matching parentheses, like '()' or '[]' or '{}'.
If you find a pair, remove it from the string.
Repeat steps 2 and 3 until you can't find any more matching pairs next to each other.
If, after removing all possible pairs, the string is empty, then the original string was valid.
However, if there are any parentheses left in the string after removing all possible pairs, then the original string was invalid.

Code Implementation

def is_valid_parentheses_brute_force(input_string):
    mutable_string = list(input_string)

    while True:
        found_match = False
        index = 0

        while index < len(mutable_string) - 1:
            # Check for matching parentheses pairs

            if (mutable_string[index] == '(' and mutable_string[index + 1] == ')') or \
               (mutable_string[index] == '[' and mutable_string[index + 1] == ']') or \
               (mutable_string[index] == '{' and mutable_string[index + 1] == '}'):

                # Remove the matching pairs
                mutable_string.pop(index + 1)
                mutable_string.pop(index)
                found_match = True

                # Reset the index to the beginning
                index = 0
                continue
            index += 1

        # If no matching pairs were found, break the loop
        if not found_match:
            break

    # Check if the string is empty after removing matching pairs
    if not mutable_string:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

O(n²) – The provided algorithm iteratively searches for and removes matching adjacent parentheses. In the worst-case scenario, we might have to iterate through the string multiple times to remove all matching pairs. The outer loop implicitly continues as long as matching pairs are found. The inner loop, which searches for matching pairs, iterates through the string of size n. Because, in the worst case, this process may repeat up to n/2 times to remove all pairs, the time complexity becomes O(n * n/2) which simplifies to O(n²).

Space Complexity

O(N) – The brute force approach described iteratively removes matching parentheses from the string. In the worst-case scenario, where the input string contains no matching pairs initially or where the algorithm ends up reconstructing a potentially near-identical string after each removal, the modified string may require up to N space in each iteration, where N is the length of the original input string. This stems from the string manipulation that occurs each time a pair is removed, where a new string needs to be constructed. Therefore, the auxiliary space complexity is O(N).

Optimal Solution

Approach

The best way to check if parentheses are valid is to use a stack-like structure to keep track of opening parentheses. We'll go through the input step by step, making sure each closing parenthesis has a matching opening parenthesis.

Here's how the algorithm would work step-by-step:

Imagine having a container where you'll store opening parentheses.
Go through each parenthesis in the given text, one by one.
If you find an opening parenthesis, put it into the container.
If you find a closing parenthesis, check if the container is empty. If it is, that means you have an unmatched closing parenthesis, so the arrangement is invalid.
If the container is not empty, check if the closing parenthesis matches the last opening parenthesis you put in the container. If they match, remove the opening parenthesis from the container. If they don't match, the arrangement is invalid.
After checking all parentheses, if the container is empty, it means every opening parenthesis has a matching closing parenthesis, so the arrangement is valid. If the container is not empty, it means there are unmatched opening parentheses, so the arrangement is invalid.

Code Implementation

def isValid(input_string):    parenthesis_stack = []
    parenthesis_map = {
        ')': '(',
        ']': '[',
        '}': '{'
    }
    for char in input_string:
        if char in parenthesis_map:
            # Closing parenthesis found, check for match

            if not parenthesis_stack or parenthesis_stack[-1] != parenthesis_map[char]:
                return False
            parenthesis_stack.pop()
        else:
            # Opening parenthesis found, add to stack

            parenthesis_stack.append(char)

    # Stack must be empty for valid parentheses

    return not parenthesis_stack

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of length n exactly once. Inside the loop, it performs constant-time operations such as checking if a character is an opening or closing parenthesis, pushing onto a stack, or popping from a stack. Since the number of operations is directly proportional to the input size n, the time complexity is O(n).

Space Complexity

O(N) – The provided solution uses a container (implicitly a stack) to store opening parentheses. In the worst-case scenario, the input string consists entirely of opening parentheses. In this case, all N characters of the input string would be stored in the stack. Thus, the auxiliary space used grows linearly with the input size N, resulting in a space complexity of O(N).

Edge Cases

Case	How to Handle
Empty string input	Return true since an empty string is considered valid.
Null string input	Return true if a null string is considered valid; otherwise, throw an IllegalArgumentException or return false.
String with a single opening bracket	Return false, as there's no corresponding closing bracket.
String with a single closing bracket	Return false, as there's no corresponding opening bracket.
String with mismatched brackets, e.g., '(]'	Return false, as the closing bracket doesn't match the last opened bracket.
String with correctly nested brackets but incorrect order, e.g., '(){}'	The stack should not be empty at the end if order is incorrect, resulting in returning false.
String with only opening brackets, e.g., '((({'	The stack will not be empty if only opening brackets exist, leading to returning false.
Very long string (potential stack overflow)	Ensure the stack implementation used (explicit or implicit) is memory efficient, especially for deep nesting, and avoid unbounded recursion.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` be empty or null? If so, what should I return?
Are there any characters other than '(', ')', '{', '}', '[', and ']' in the input string? If so, how should I handle them?
Is the length of the string `s` constrained? This could impact space complexity considerations.
If the string is invalid, are there specific error codes or exceptions I should raise, or is returning `false` sufficient?
By 'correct order', do you mean that for every opening bracket, there must be a corresponding closing bracket of the same type appearing later in the string, and nested brackets must also follow this rule?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Look at the entire string of parentheses.
Find a pair of adjacent matching parentheses, like '()' or '[]' or '{}'.
If you find a pair, remove it from the string.
Repeat steps 2 and 3 until you can't find any more matching pairs next to each other.
If, after removing all possible pairs, the string is empty, then the original string was valid.
However, if there are any parentheses left in the string after removing all possible pairs, then the original string was invalid.

Code Implementation

def is_valid_parentheses_brute_force(input_string):
    mutable_string = list(input_string)

    while True:
        found_match = False
        index = 0

        while index < len(mutable_string) - 1:
            # Check for matching parentheses pairs

            if (mutable_string[index] == '(' and mutable_string[index + 1] == ')') or \
               (mutable_string[index] == '[' and mutable_string[index + 1] == ']') or \
               (mutable_string[index] == '{' and mutable_string[index + 1] == '}'):

                # Remove the matching pairs
                mutable_string.pop(index + 1)
                mutable_string.pop(index)
                found_match = True

                # Reset the index to the beginning
                index = 0
                continue
            index += 1

        # If no matching pairs were found, break the loop
        if not found_match:
            break

    # Check if the string is empty after removing matching pairs
    if not mutable_string:
        return True
    else:
        return False

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine having a container where you'll store opening parentheses.
Go through each parenthesis in the given text, one by one.
If you find an opening parenthesis, put it into the container.
If you find a closing parenthesis, check if the container is empty. If it is, that means you have an unmatched closing parenthesis, so the arrangement is invalid.
If the container is not empty, check if the closing parenthesis matches the last opening parenthesis you put in the container. If they match, remove the opening parenthesis from the container. If they don't match, the arrangement is invalid.
After checking all parentheses, if the container is empty, it means every opening parenthesis has a matching closing parenthesis, so the arrangement is valid. If the container is not empty, it means there are unmatched opening parentheses, so the arrangement is invalid.

Code Implementation

def isValid(input_string):    parenthesis_stack = []
    parenthesis_map = {
        ')': '(',
        ']': '[',
        '}': '{'
    }
    for char in input_string:
        if char in parenthesis_map:
            # Closing parenthesis found, check for match

            if not parenthesis_stack or parenthesis_stack[-1] != parenthesis_map[char]:
                return False
            parenthesis_stack.pop()
        else:
            # Opening parenthesis found, add to stack

            parenthesis_stack.append(char)

    # Stack must be empty for valid parentheses

    return not parenthesis_stack

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty string input	Return true since an empty string is considered valid.
Null string input	Return true if a null string is considered valid; otherwise, throw an IllegalArgumentException or return false.
String with a single opening bracket	Return false, as there's no corresponding closing bracket.
String with a single closing bracket	Return false, as there's no corresponding opening bracket.
String with mismatched brackets, e.g., '(]'	Return false, as the closing bracket doesn't match the last opened bracket.
String with correctly nested brackets but incorrect order, e.g., '(){}'	The stack should not be empty at the end if order is incorrect, resulting in returning false.
String with only opening brackets, e.g., '((({'	The stack will not be empty if only opening brackets exist, leading to returning false.
Very long string (potential stack overflow)	Ensure the stack implementation used (explicit or implicit) is memory efficient, especially for deep nesting, and avoid unbounded recursion.