Solve three LeetCode coding problems
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### 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/
Quick Answer: The trio of problems — Minimum Remove to Make Valid Parentheses, Making a Large Island, and Binary Tree Right Side View — evaluates algorithmic problem-solving, proficiency with core data structures (strings, grids/graphs, and trees), and awareness of time and space complexity.
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
Input: ))((
Expected Output:
Input: a)b(c)d
Expected Output: ab(c)d
Input: lee(t(c)o)de)
Expected Output: lee(t(c)o)de
Input: ((a)
Expected Output: (a)
Input: a((b
Expected Output: ab
Solution
def min_remove_to_make_valid(s: str) -> str:
to_remove = set()
stack = [] # stores indices of '('
for i, ch in enumerate(s):
if ch == '(':
stack.append(i)
elif ch == ')':
if stack:
stack.pop()
else:
to_remove.add(i)
# Any indices left in stack are unmatched '('
to_remove.update(stack)
# Build result skipping indices in to_remove
res_chars = []
for i, ch in enumerate(s):
if i not in to_remove:
res_chars.append(ch)
return ''.join(res_chars)
Explanation
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).
Hints
- Use a stack to store indices of '('; when encountering ')', pop if possible, otherwise mark it for removal.
- After the first pass, any indices left in the stack are unmatched '(' and should be removed.
- Build the result by skipping all indices marked for removal. This ensures minimal removals.