How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Solve LeetCode stack and tree problems

Quick Overview

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.

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: ()()

Solution

def min_remove_to_make_valid(s: str) -> str:
    chars = list(s)
    stack = []  # indices of '('
    for i, ch in enumerate(chars):
        if ch == '(':  # potential opener
            stack.append(i)
        elif ch == ')':
            if stack:
                stack.pop()  # match with a previous '('
            else:
                chars[i] = ''  # remove unmatched ')'
    # remove any unmatched '('
    for i in stack:
        chars[i] = ''
    return ''.join(chars)

Explanation

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

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.

Last updated: Mar 29, 2026

Loading coding console...

Quick Overview

Solve LeetCode stack and tree problems

Company: Meta

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

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: ()()

Solution

def min_remove_to_make_valid(s: str) -> str:
    chars = list(s)
    stack = []  # indices of '('
    for i, ch in enumerate(chars):
        if ch == '(':  # potential opener
            stack.append(i)
        elif ch == ')':
            if stack:
                stack.pop()  # match with a previous '('
            else:
                chars[i] = ''  # remove unmatched ')'
    # remove any unmatched '('
    for i in stack:
        chars[i] = ''
    return ''.join(chars)

Explanation

Time complexity: O(n). Space complexity: O(n).

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.

Last updated: Mar 29, 2026

Loading coding console...