FastPrep
Problem · String

Minimum Parenthesis Removals and Their Indices

Learn this problem
● EasyDoorDash logoDoorDashFULLTIMEONSITE INTERVIEW

Problem statement

Given a string containing only ( and ), match each closing parenthesis with the most recent unmatched opening parenthesis. Return every index left unmatched by that scan.

  • The returned indices must be in ascending order.
  • The array length is the minimum possible number of deletions.

Function

minimumRemovalIndices(s: String) → int[]

Examples

Example 1

s = "())(()"return = [2,3]

Index 2 is an unmatched closing parenthesis and index 3 is the unmatched opening parenthesis left after the scan.

Example 2

s = "))(("return = [0,1,2,3]

Every parenthesis is unmatched.

Constraints

  • s contains only ( and ).

More DoorDash problems

drafts saved locally
public int[] minimumRemovalIndices(String s) {
    // TODO: return all unmatched parenthesis indices in ascending order.
}
s"())(()"
expected[2,3]
checking account