Solve LeetCode stack and tree problems
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
LeetCode 1249. Minimum Remove to Make Valid Parentheses LeetCode 863. All Nodes Distance K in Binary Tree
https://leetcode.com/problems/minimum-remove-to-make-valid-parentheses/description/ https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/description/
Quick Answer: This item evaluates proficiency in string processing and tree/graph algorithms, testing competencies such as handling parentheses validity and computing node distances in binary trees. It is commonly asked in Coding & Algorithms interviews to assess core data structures and algorithmic problem-solving, emphasizing practical application of techniques alongside conceptual understanding.
Given a string s consisting of '(', ')', and lowercase English letters, remove the minimum number of parentheses to make the parentheses valid. Letters must remain in their original order; only delete characters. Return the resulting string. A parentheses string is valid if every '(' has a corresponding ')' and the pairs are properly nested. If multiple answers with the minimum number of removals exist, return any one of them.
Constraints
- 1 <= len(s) <= 100000
- s contains only '(', ')', and lowercase letters 'a'-'z'
- Return any valid result with the minimum number of removals
- Aim for O(n) time and O(n) extra space or better
Examples
Input: lee(t(c)o)de)
Expected Output: lee(t(c)o)de
Input: a)b(c)d
Expected Output: ab(c)d
Input: ))((
Expected Output:
Input: abc
Expected Output: abc
Input: ((a)
Expected Output: (a)
Input: ())()(((
Expected Output: ()()
Hints
- Use a stack to store indices of '(' and mark unmatched ')' for removal.
- After the first pass, any indices left in the stack are unmatched '('; remove them.
- Building the result with a list and joining at the end is more efficient than repeated string concatenation.