We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Add to Make Parentheses Valid

Number: 957

Difficulty: Medium

Paid? No

Companies: Meta, Amazon, Bloomberg, Google, TikTok, Walmart Labs, Apple, Nvidia, tcs

Problem Description

Given a string s consisting only of the characters '(' and ')', determine the minimum number of moves required to make the string valid. A valid string is defined as:

  • An empty string,
  • A string that can be formed by the concatenation of two valid strings, or
  • A string that can be written as (A), where A is a valid string. In one move, you can insert a parenthesis at any position in the string.

Key Insights

  • Use a counter to track the number of unmatched '(' characters.
  • When encountering a ')', if there is no preceding unmatched '(', it indicates an imbalance that requires inserting an '('.
  • After processing the entire string, any remaining unmatched '(' will require inserting the same number of closing parentheses.
  • The total moves is the sum of insertions needed for unmatched ')' and unmatched '('.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. Space Complexity: O(1)

Solution

The solution iterates through the entire string using a single pass. A counter (named count) is incremented for every '(' encountered, representing an imbalance. When a ')' is encountered, if the counter is greater than zero, it implies a matching '(' exists, so the counter is decremented; if not, it indicates an unmatched ')' and requires an insertion, so a moves counter is incremented. After processing all characters, any remaining count of '(' represents unmatched openings, and the same number of moves must be added. This greedy approach ensures we account for all imbalances with a minimum number of moves using constant space.

Code Solutions

# Function to determine the minimum moves required
def minAddToMakeValid(s):
    moves = 0  # Counts the required insertions for unmatched ')'
    count = 0  # Counts unmatched '(' characters
    for char in s:
        if char == '(':
            count += 1  # Increase count for an open parenthesis
        elif char == ')':
            # If no matching open, it's an error, need one move to balance
            if count == 0:
                moves += 1
            else:
                count -= 1  # Found a matching pair
    # Add moves needed for any leftover unmatched '('
    return moves + count

# Example usage:
print(minAddToMakeValid("())"))  # Expected output: 1
print(minAddToMakeValid("((("))  # Expected output: 3
← Back to All Questions