Coding questions · Meta
Solve LeetCode stack and tree problems
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.
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/
Minimum Remove to Make Parentheses Valid
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
Example 1
Input: s = "lee(t(c)o)de)"
Output: lee(t(c)o)de
Explanation: Remove the last ')' to balance the parentheses.
Example 2
Input: s = "a)b(c)d"
Output: ab(c)d
Explanation: Remove the ')' at index 1; the remaining string is valid.
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.
Approach
Scan the string once, pushing indices of '(' onto a stack. When encountering ')', match it with the most recent '(' if possible; otherwise mark it for removal. After the scan, any remaining '(' indices in the stack are unmatched and must be removed. Finally, join the remaining characters to form the result. This removes exactly the unmatched parentheses, which is minimal.
- Time complexity: O(n)
- Space complexity: O(n)