Katkat
Back

Find the Minimum Parenthesis Deletions and Their Positions

DoorDashSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests string manipulation, stack-based parsing, and greedy logic to identify the indices of parentheses that must be removed to transform a string into a valid sequence.

Problem Statement

DoorDash uses a custom formatting tool for delivery notes that processes nested order instructions encapsulated in parentheses. A sequence of instructions is considered valid if every opening parenthesis '(' has a corresponding closing parenthesis ')' and they are properly nested.

Given a string s containing only characters '(', ')', and alphanumeric characters, identify the minimum number of parentheses that must be removed to make the string valid. If there are multiple sets of removals that result in the same minimum number of deletions, return the set of indices that is lexicographically smallest. If the resulting sets are tied, return the one that appears first when sorted index-wise.

Function Signature

def get_min_deletions(s: str) -> List[int]:

Examples

Example 1: Input: s = "a(b)c)" Output: [5] Explanation: The extra ')' at index 5 must be removed.

Example 2: Input: s = "()())" Output: [4] Explanation: Any of the three ')' could be removed to make the string valid, but removing the one at index 4 is the smallest index.

Constraints

  • 1 <= len(s) <= 10^5
  • s consists of '(', ')', and lowercase English letters.
  • Time complexity should be O(n).

Edge Cases

  • String with no parentheses: return [].
  • String with only invalid parentheses: return indices of all parentheses.
  • Already valid string: return [].

Hints

Hint 1

Use a stack to keep track of the indices of opening parentheses that are waiting to be matched.

Hint 2

During a single pass, identify ')' characters that do not have a preceding '(' and store their indices as candidates for deletion.

Hint 3

After the pass, any unmatched '(' indices remaining in the stack must also be removed to ensure validity.

Follow-up questions

  • How would you modify your solution if you were required to return the actual resulting string instead of the indices?
  • What changes are needed if the string contains multiple types of brackets, such as '[]' and '{}'?
  • How does your algorithm perform in terms of space complexity, and can it be optimized further if we only need the count of deletions?