Meta·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

May 2026Remote

Summary

Meta SWE coding round, one question on parentheses cleanup. Pretty standard string manipulation problem but the O(n) constraint meant you couldn't just brute force it.

Questions Asked (1)

Given a string containing lowercase letters and parentheses, remove the minimum number of parentheses to make the string valid. Must run in O(n) time.

Algorithms & Data Structures

Author's notes

My first instinct was a stack to track unmatched opens, then a second pass to mark unmatched closes.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a stack to track indices of unmatched parentheses, then mark those indices for removal. Alternatively, use two passes with counters to identify unmatched closing and opening parentheses. The key is to achieve O(n) time by scanning the string a constant number of times.

Pro tip: Clarify whether you need to return the valid string or just the minimum number of removals; often interviewers expect the modified string. Also, mention that multiple valid strings may exist, so any valid result is acceptable.

1. Understand the problem

Confirm that you need to remove the minimum number of parentheses to make the string valid, and that the string contains lowercase letters and parentheses. Ask if you should return the modified string or just the count.

2. Choose an approach

Decide between a stack-based method (tracking indices) or a two-pass counter method. Both achieve O(n) time and O(n) space, but the stack method directly gives the indices to remove.

3. Implement the algorithm

For stack: iterate through string, push '(' indices, pop on matching ')', and mark unmatched ')' indices. Then mark remaining '(' indices in stack. For two-pass: first pass remove unmatched ')', second pass remove unmatched '(' from the end.

4. Build the result

Create a set of indices to remove, then construct the resulting string by skipping those indices. Alternatively, build the string during the second pass.

5. Analyze complexity and test

State that time complexity is O(n) and space complexity is O(n). Walk through edge cases like empty string, all parentheses, and no parentheses.

Key Points to Mention

Use a stack to track indices of unmatched parentheses for efficient removal.
Alternatively, use two passes with counters to identify unmatched closing and opening parentheses.
Time complexity is O(n) because each character is processed a constant number of times.
Space complexity is O(n) in the worst case (e.g., all opening parentheses).
Handle edge cases: empty string, string with no parentheses, string with only parentheses.
Multiple valid strings may exist; any valid result is acceptable.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.