Jobs

Interviews

Discussions

Score of Parentheses

Medium

Asked by:

More companies

62 views

Topics:

StacksRecursion

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is based on the following rule:

"()" has score 1.
AB has score A + B, where A and B are balanced parentheses strings.
(A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

Input: s = "()"
Output: 1

Example 2:

Input: s = "(())"
Output: 2

Example 3:

Input: s = "()()"
Output: 2

Constraints:

2 <= s.length <= 50
s consists of only '(' and ')'.
s is a balanced parentheses string.

Try coding it in LeetCode

Score of Parentheses

Medium

Asked by:

62 views

Topics:

StacksRecursion

Given a balanced parentheses string s, return the score of the string.

The score of a balanced parentheses string is based on the following rule:

"()" has score 1.
AB has score A + B, where A and B are balanced parentheses strings.
(A) has score 2 * A, where A is a balanced parentheses string.

Example 1:

Input: s = "()"
Output: 1

Example 2:

Input: s = "(())"
Output: 2

Example 3:

Input: s = "()()"
Output: 2

Constraints:

2 <= s.length <= 50
s consists of only '(' and ')'.
s is a balanced parentheses string.

Try coding it in LeetCode

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 contain characters other than '(' and ')'?
Can the input string be empty or null?
Is the input string guaranteed to be balanced, meaning that every opening parenthesis has a corresponding closing parenthesis?
What is the maximum length of the input string?
Should I assume that the parentheses string will always be properly nested, or do I need to handle cases with invalid nesting (e.g., ')((')?

Brute Force Solution

Approach

The brute force approach to the parentheses scoring problem essentially tries to directly follow the scoring rules by recursively breaking down the input. We look for the innermost balanced parentheses and compute their score.

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

Look at the whole string of parentheses.
Find the first complete, balanced set of parentheses. A balanced set starts with an open parenthesis and ends with a matching close parenthesis, with no extra open or close parentheses in between.
Calculate the score for that set. If it's just '()', the score is 1.
Remove that set from the string. You're left with potentially smaller, separated strings.
Repeat steps 2-4 for each of the remaining strings.
If you find a long, balanced set that contains other balanced sets inside, first calculate the scores for the inner sets.
Multiply the combined score of all internal balanced sets by 2 if the whole string matches the form '(A)' where A is a sequence of balanced parentheses.
Add up the scores of all the individual and multiplied sets to get the final score for the entire string.

Code Implementation

def score_of_parentheses_brute_force(parentheses_string):
    if not parentheses_string:
        return 0

    balance = 0
    for index, character in enumerate(parentheses_string):
        if character == '(': 
            balance += 1
        else:
            balance -= 1

        if balance == 0:
            # Found a balanced substring.
            if index == len(parentheses_string) - 1:
                if parentheses_string[0] == '(' and parentheses_string[-1] == ')':
                    substring = parentheses_string[1:len(parentheses_string) - 1]

                    # Recursively calculate the score for inner string.
                    return 2 * score_of_parentheses_brute_force(substring)
                else:
                    return 1
            else:
                # Calculate the score for this substring and the remaining part
                substring = parentheses_string[:index + 1]
                remaining_string = parentheses_string[index + 1:]
                return score_of_parentheses_brute_force(substring) + \
                       score_of_parentheses_brute_force(remaining_string)

    return 0

Big(O) Analysis

Time Complexity

O(n^2) – The algorithm iterates through the string of length n to find balanced parentheses. In the worst-case scenario, for each open parenthesis, it might have to traverse the rest of the string to find the matching closing parenthesis. This nested iteration leads to a cost proportional to n * n/2, where on average half the string is checked to find matching pairs of parens. Therefore, the time complexity is O(n^2).

Space Complexity

O(N) – The brute force approach uses recursion. In the worst case, where the input string consists of nested parentheses like '((((...))))', the recursion depth can reach N, where N is the length of the input string. Each recursive call consumes stack space for its local variables and return address. Therefore, the auxiliary space used by the recursion stack is proportional to N, resulting in a space complexity of O(N).

Optimal Solution

Approach

The problem involves calculating a score based on the structure of nested parentheses. The most effective way to do this is to keep track of the 'depth' of the parentheses as you go, since the depth influences the score of inner pairs. We can then derive the score by considering the powers of 2 based on the nesting levels.

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

Start reading the string of parentheses from left to right.
Keep track of the 'depth' or nesting level. Every time you see an opening parenthesis, increase the depth, and every time you see a closing parenthesis, decrease the depth.
Whenever you find a pair of directly adjacent parentheses '()', its score is determined by the current depth. Specifically, it is 2 raised to the power of the depth.
Add up the scores of all these pairs, taking into account their depth during the process. This will give you the total score.
The final sum represents the score for the entire string of parentheses.

Code Implementation

def score_of_parentheses(parenthesis_string):
    string_length = len(parenthesis_string)
    current_depth = 0
    total_score = 0

    for i in range(string_length):
        if parenthesis_string[i] == '(': # Increase depth for opening parenthesis
            current_depth += 1

        elif parenthesis_string[i] == ')':
            current_depth -= 1

            # If adjacent pair, calculate score based on current depth
            if parenthesis_string[i-1] == '(': 
                total_score += 2 ** current_depth

    return total_score

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input string of parentheses once. The depth is updated in constant time for each parenthesis encountered. The score for each '()' pair is calculated based on the current depth, also a constant-time operation. Since we process each of the n characters in the input string once, the overall time complexity is O(n).

Space Complexity

O(1) – The algorithm primarily uses a single integer variable to track the 'depth' of the parentheses and another integer variable to accumulate the 'score'. The space required for these variables remains constant regardless of the length of the input string. Therefore, the auxiliary space complexity is independent of the input size N (where N is the length of the parentheses string). This means the algorithm uses constant extra space.

Edge Cases

Case	How to Handle
Null or empty string input	Return 0 as the score for an empty expression is defined as 0.
Input string with only one character	Return 0 since a single parenthesis is not a valid expression.
String with mismatched parentheses, like '(()'	The solution should handle mismatched parentheses gracefully, likely calculating the score of the valid prefix.
Deeply nested parentheses '((((((())))))))'	Be mindful of stack overflow in recursive approaches or integer overflow with large scores.
String with a single level of nested parentheses '()()()'	The solution should correctly calculate the score as the sum of individual '()' scores.
Maximum length input string	Ensure the algorithm's time and space complexity are efficient enough to handle large input sizes without exceeding memory or time limits.
Integer overflow when calculating score	Use a data type with a larger range (e.g., long) or apply modulo operation if the problem specifies it.
Input string with very unbalanced nested structures	The solution must correctly calculate the score by properly handling different levels of nesting depth.

Null or empty string input

How to Handle:

Return 0 as the score for an empty expression is defined as 0.

Input string with only one character

How to Handle:

Return 0 since a single parenthesis is not a valid expression.

String with mismatched parentheses, like '(()'

How to Handle:

The solution should handle mismatched parentheses gracefully, likely calculating the score of the valid prefix.

Deeply nested parentheses '((((((())))))))'

How to Handle:

Be mindful of stack overflow in recursive approaches or integer overflow with large scores.

String with a single level of nested parentheses '()()()'

How to Handle:

The solution should correctly calculate the score as the sum of individual '()' scores.

Maximum length input string

How to Handle:

Ensure the algorithm's time and space complexity are efficient enough to handle large input sizes without exceeding memory or time limits.

Integer overflow when calculating score

How to Handle:

Use a data type with a larger range (e.g., long) or apply modulo operation if the problem specifies it.

Input string with very unbalanced nested structures

How to Handle:

The solution must correctly calculate the score by properly handling different levels of nesting depth.

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 contain characters other than '(' and ')'?
Can the input string be empty or null?
Is the input string guaranteed to be balanced, meaning that every opening parenthesis has a corresponding closing parenthesis?
What is the maximum length of the input string?
Should I assume that the parentheses string will always be properly nested, or do I need to handle cases with invalid nesting (e.g., ')((')?

Brute Force Solution

Approach

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

Look at the whole string of parentheses.
Find the first complete, balanced set of parentheses. A balanced set starts with an open parenthesis and ends with a matching close parenthesis, with no extra open or close parentheses in between.
Calculate the score for that set. If it's just '()', the score is 1.
Remove that set from the string. You're left with potentially smaller, separated strings.
Repeat steps 2-4 for each of the remaining strings.
If you find a long, balanced set that contains other balanced sets inside, first calculate the scores for the inner sets.
Multiply the combined score of all internal balanced sets by 2 if the whole string matches the form '(A)' where A is a sequence of balanced parentheses.
Add up the scores of all the individual and multiplied sets to get the final score for the entire string.

Code Implementation

def score_of_parentheses_brute_force(parentheses_string):
    if not parentheses_string:
        return 0

    balance = 0
    for index, character in enumerate(parentheses_string):
        if character == '(': 
            balance += 1
        else:
            balance -= 1

        if balance == 0:
            # Found a balanced substring.
            if index == len(parentheses_string) - 1:
                if parentheses_string[0] == '(' and parentheses_string[-1] == ')':
                    substring = parentheses_string[1:len(parentheses_string) - 1]

                    # Recursively calculate the score for inner string.
                    return 2 * score_of_parentheses_brute_force(substring)
                else:
                    return 1
            else:
                # Calculate the score for this substring and the remaining part
                substring = parentheses_string[:index + 1]
                remaining_string = parentheses_string[index + 1:]
                return score_of_parentheses_brute_force(substring) + \
                       score_of_parentheses_brute_force(remaining_string)

    return 0

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start reading the string of parentheses from left to right.
Keep track of the 'depth' or nesting level. Every time you see an opening parenthesis, increase the depth, and every time you see a closing parenthesis, decrease the depth.
Whenever you find a pair of directly adjacent parentheses '()', its score is determined by the current depth. Specifically, it is 2 raised to the power of the depth.
Add up the scores of all these pairs, taking into account their depth during the process. This will give you the total score.
The final sum represents the score for the entire string of parentheses.

Code Implementation

def score_of_parentheses(parenthesis_string):
    string_length = len(parenthesis_string)
    current_depth = 0
    total_score = 0

    for i in range(string_length):
        if parenthesis_string[i] == '(': # Increase depth for opening parenthesis
            current_depth += 1

        elif parenthesis_string[i] == ')':
            current_depth -= 1

            # If adjacent pair, calculate score based on current depth
            if parenthesis_string[i-1] == '(': 
                total_score += 2 ** current_depth

    return total_score

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return 0 as the score for an empty expression is defined as 0.
Input string with only one character	Return 0 since a single parenthesis is not a valid expression.
String with mismatched parentheses, like '(()'	The solution should handle mismatched parentheses gracefully, likely calculating the score of the valid prefix.
Deeply nested parentheses '((((((())))))))'	Be mindful of stack overflow in recursive approaches or integer overflow with large scores.
String with a single level of nested parentheses '()()()'	The solution should correctly calculate the score as the sum of individual '()' scores.
Maximum length input string	Ensure the algorithm's time and space complexity are efficient enough to handle large input sizes without exceeding memory or time limits.
Integer overflow when calculating score	Use a data type with a larger range (e.g., long) or apply modulo operation if the problem specifies it.
Input string with very unbalanced nested structures	The solution must correctly calculate the score by properly handling different levels of nesting depth.

Null or empty string input

How to Handle:

Return 0 as the score for an empty expression is defined as 0.

Input string with only one character

How to Handle:

Return 0 since a single parenthesis is not a valid expression.

String with mismatched parentheses, like '(()'

How to Handle:

The solution should handle mismatched parentheses gracefully, likely calculating the score of the valid prefix.

Deeply nested parentheses '((((((())))))))'

How to Handle:

Be mindful of stack overflow in recursive approaches or integer overflow with large scores.

String with a single level of nested parentheses '()()()'

How to Handle:

The solution should correctly calculate the score as the sum of individual '()' scores.

Maximum length input string

How to Handle:

Ensure the algorithm's time and space complexity are efficient enough to handle large input sizes without exceeding memory or time limits.

Integer overflow when calculating score

How to Handle:

Use a data type with a larger range (e.g., long) or apply modulo operation if the problem specifies it.

Input string with very unbalanced nested structures

How to Handle:

The solution must correctly calculate the score by properly handling different levels of nesting depth.