Solve three LeetCode coding problems

Question

LeetCode 1249. Minimum Remove to Make Valid Parentheses LeetCode 827. Making A Large Island LeetCode 199. Binary Tree Right Side View

https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/ https://leetcode.com/problems/making-a-large-island/description/ https://leetcode.com/problems/binary-tree-right-side-view/description/

Remove Minimum to Balance Parentheses

Given a string s consisting of '(' , ')' , and lowercase English letters, remove the minimum number of parentheses so that the resulting string is a valid parentheses string. Letters must remain in their original relative order. Return any valid result if multiple exist.

Constraints

• 0 <= len(s) <= 100000
• s contains only '(', ')', and lowercase English letters (a-z)
• Return any valid string after removing the minimum number of parentheses
• If s is already valid, return s unchanged

Examples

Example 1

Input: Input: s = 'lee(t(c)o)de)'
Output: Output: 'lee(t(c)o)de'

Explanation: The last ')' has no matching '('. Removing it yields a valid string.

Example 2

Input: Input: s = 'a)b(c)d'
Output: Output: 'ab(c)d'

Explanation: The ')' after 'a' is unmatched and must be removed.

Hints

1. Use a stack to store indices of '('; when encountering ')', pop if possible, otherwise mark it for removal.
2. After the first pass, any indices left in the stack are unmatched '(' and should be removed.
3. Build the result by skipping all indices marked for removal. This ensures minimal removals.

Approach

Traverse the string and push indices of '(' onto a stack. For each ')', if the stack is non-empty, pop to match it; otherwise, mark that ')' index for removal. After the pass, any indices left in the stack correspond to unmatched '(' and are also marked for removal. Finally, build the result by skipping all marked indices. This removes exactly the unmatched parentheses, ensuring the minimum number of deletions.

• Time complexity: O(n)
• Space complexity: O(n)