What is the brute force approach and complexity for Minimum Remove to Make Valid Parentheses?

Scan with a counter, delete the first bad bracket found, rescan with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Minimum Remove to Make Valid Parentheses?

Push indices of '('; unmatched ')' marked now, leftover '(' marked at the end with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Minimum Remove to Make Valid Parentheses?

Look for key signals in the prompt: "remove the minimum number of parentheses" indicates Keep every bracket that can be matched; delete only the ones that can't → run the matching and see who is left over.; "make the string valid" indicates Same matching rule as Valid Parentheses: a `)` closes the most recent open `(`.; "return the string" indicates We must know **where** the bad brackets are, not just how many → store indices on the stack..

Minimum Remove to Make Valid Parentheses

Medium·LeetCode #1249 Pro OnlySlight Variation

LeetCode

Problem Statement

You are given a string s of lowercase letters and the brackets ( and ).

Delete the fewest brackets possible so that the brackets in the string become valid, and return the resulting string. Letters are never deleted.

Valid means: every ( has a ) after it that closes it, and every ) closes some ( before it. A string with no brackets is valid. If there are several correct answers, return any one of them.

Input

A string s of lowercase letters, ( and ).

Output

A valid string made by deleting as few brackets as possible from s.

Example 1

Input: s = "lee(t(c)o)de)"

Output: "lee(t(c)o)de"

The last ) has nothing left to close, so it goes. "lee(t(co)de)" or "lee(t(c)ode)" would also be accepted.

Example 2

Input: s = "a)b(c)d"

Output: "ab(c)d"

The first ) comes before any (, so it can never be matched.

Example 3

Input: s = "))(("

Output: ""

No bracket can be matched, so all four are deleted.

Constraints

• 1 ≤ s.length ≤ 10^5
• s[i] is '(', ')' or a lowercase English letter

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“remove the minimum number of parentheses”

→ Keep every bracket that can be matched; delete only the ones that can't → run the matching and see who is left over.

“make the string valid”

→ Same matching rule as Valid Parentheses: a `)` closes the most recent open `(`.

“return the string”

→ We must know **where** the bad brackets are, not just how many → store indices on the stack.

Approach Complexity Ladder

Brute Force — fix one bad bracket at a timeO(N²)O(1)

Scan with a counter, delete the first bad bracket found, rescan

Better — two counter passesO(N)O(N)

Left→right drop extra ')', then right→left drop extra '('

Optimal — stack of indicesO(N)O(N)

Push indices of '('; unmatched ')' marked now, leftover '(' marked at the end

Brute Force Intuition

Scan with a counter of open brackets. The first ) that arrives while the counter is 0 is surely bad: delete it and scan again from the start. If a scan finds no bad ) but the counter ends above 0, some ( were never closed; the last ( is surely one of them, so delete it and scan again. Stop when the string is valid.

Recognition rule for this sub-pattern:

Opening things wait on the stack until their closing partner arrives.

Remember this · Stack

Trigger

Matching pairs, nested structure, undo, evaluating expressions, "the last one wins".

Think

Does each new element need to look at the most recent unresolved element?

Key question

What does an item on the stack represent, and when does it get resolved?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Stack translate into production architectures and low-level memory mechanics.

LLD Architecture

Expression Parser & Interpreter Pattern

Abstract syntax tree evaluation and operator precedence parsing.

Explore Track

C++ Internals

Stack vs Heap Segments

Call stack frame layout, return addresses, and buffer overflow prevention.

Explore Track

Remove All Adjacent Duplicates In String Decode String