Minimum Remove to Make Valid Parentheses - Practice Coding Problems

Minimum Remove to Make Valid Parentheses - Problem

String Stack Medium

Given a string s containing '(', ')' and lowercase English characters, your task is to remove the minimum number of parentheses to make the resulting string valid.

A valid parentheses string is defined as:

The empty string, or contains only lowercase characters
It can be written as AB (A concatenated with B), where A and B are valid strings
It can be written as (A), where A is a valid string

Return any valid string after removing the minimum number of parentheses.

Input & Output

Example 1 — Extra Closing Parenthesis

$ Input: s = "()())"

› Output: "()()"

💡 Note: Remove the extra closing parenthesis at position 4. The string "()()" has valid balanced parentheses.

Example 2 — Extra Opening Parenthesis

$ Input: s = "((("

› Output: ""

💡 Note: All three opening parentheses are unmatched, so remove all of them to get empty string.

Example 3 — Mixed with Letters

$ Input: s = "(a))b)"

› Output: "(a)b"

💡 Note: Remove one closing parenthesis after 'a' and the closing parenthesis after 'b' to make it valid.

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is either '(' , ')' or lowercase English letter

Visualization

Tap to expand

Understanding the Visualization

Input

String with unmatched parentheses: "()())"

Process

Identify and remove unmatched brackets

Output

Valid parentheses string: "()()"

Key Takeaway

🎯 Key Insight: Use a counter to track unmatched opening brackets and immediately skip unmatched closing brackets

Asked in

f Facebook 65 G Google 45 a Amazon 38

The key insight is to use a two-pass approach to identify and remove unmatched parentheses. The optimal solution uses counters to track unmatched brackets without extra space. Time: O(n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Approach	O(n)	O(n)	Use stack to track positions of unmatched opening parentheses
Brute Force - Try All Combinations	O(2^n)	O(n)	Generate all possible subsequences and check which ones are valid
Two-Pass Optimal	O(n)	O(1)	Two passes: count unmatched brackets, then build result string

Stack-Based Approach — Algorithm Steps

Traverse string and use stack to track unmatched opening parentheses
Mark positions of all unmatched parentheses (both opening and closing)
Build result string by skipping marked positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan & Stack

Push opening brackets, pop for matching closing

Mark Unmatched

Mark unmatched closing and remaining opening brackets

Build Result

Construct string skipping marked positions

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* solution(char* s) {
    int len = strlen(s);
    int* stack = malloc(len * sizeof(int));
    int top = -1;
    int* toRemove = calloc(len, sizeof(int));
    
    // First pass: find unmatched parentheses
    for (int i = 0; i < len; i++) {
        if (s[i] == '(') {
            stack[++top] = i;
        } else if (s[i] == ')') {
            if (top >= 0) {
                top--;
            } else {
                toRemove[i] = 1; // unmatched closing
            }
        }
    }
    
    // Add remaining unmatched opening parentheses
    while (top >= 0) {
        toRemove[stack[top--]] = 1;
    }
    
    // Build result string
    char* result = malloc((len + 1) * sizeof(char));
    int resultIndex = 0;
    for (int i = 0; i < len; i++) {
        if (!toRemove[i]) {
            result[resultIndex++] = s[i];
        }
    }
    result[resultIndex] = '\0';
    
    free(stack);
    free(toRemove);
    return result;
}

int main() {
    char s[100001];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    char* result = solution(s);
    printf("%s\n", result);
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through string plus one pass to build result

✓ Linear Growth

Space Complexity

O(n)

Stack can store up to n indices, plus boolean array of size n

⚡ Linearithmic Space

85.4K Views

High Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler