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
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.