Fueled on Bacon

FOB
Blog

Minimum Remove to Make Valid Parentheses – LeetCode Solution

Original problem statement here.

This is a straightforward array problem.

The goal is to remove the minimum number of parentheses from a string so that the resulting string has a valid set of parentheses. It’s just fancy bean counting with arrays, and it requires knowing a couple gotchas about JavaScript.

The Solution

First of all here’s my solution. But this isn’t where I started.

/**
 * @param {string} s
 * @return {string}
 */
var minRemoveToMakeValid = function(s) {
  let chars = s.split("")
  let open = []  
  let close = []
  for(let i = 0; i < chars.length; i++){
    if(chars[i] == "("){
      open.push(i)
    }
    if(chars[i] == ")"){
      close.push(i)
      if(close.length > open.length){
        chars[i] = null
        close.pop()
      }
    }
  }
  while(open.length > close.length){
    const curr = open.pop()
    chars[curr] = null
  }
  return chars.filter(ch => ch !== null).join("")
};

How I started

I started the problem like this.

/**
 * @param {string} s
 * @return {string}
 */
var minRemoveToMakeValid = function(s) {
  let chars = s.split("")
  let open = 0
  let close = 0
  for(let i = 0; i < chars.length; i++){
    if(chars[i] == "("){
      open++
    }
    if(chars[i] == ")"){
      close++
    }
  }
  
};

My first thought was “I have a string, and I need to keep track of how many open and close parentheses happen.”

From doing lots of problems, I immediately remembered that you can’t just pop, slice, and push to a string like an array. You first have to split it into characters. So for problems like this, get used to writing “.split()”

What are my conditions?

The next thing I had to to figure out was, “What are my conditions?”

The basic condition for success is that the number of open parens has to be the same as the number of close parens. So we know that by the time we return something, that has to be true.

I also know that if I encounter a close paren without a matching open paren, I can just throw it away. (Ex: “))))” => “”) The number of open parens always has to be greater than or equal to the number of close parens. Whereas, until we reach the end of the array, we don’t know much about the validity of our open parens.

So lets say I have a case where I have too many open parens after I finish my first pass. It would help if I knew the indexes of all those parens so I could delete them down to the point where open parens = close parens.

Well that means I need arrays tracking indexes not counters.

This is pretty much sufficient to solve the problem. Assuming we had these intuitions, we can solve the problem outright.

Wrapping Up

Here’s that solution again. You can see the counters become arrays.

You can also see that I just use “null” as my placeholder for deleted characters. And then to return my response, I filter and join the array I operated on.

/**
 * @param {string} s
 * @return {string}
 */
var minRemoveToMakeValid = function(s) {
  let chars = s.split("")
  let open = []  
  let close = []
  for(let i = 0; i < chars.length; i++){
    if(chars[i] == "("){
      open.push(i)
    }
    if(chars[i] == ")"){
      close.push(i)
      if(close.length > open.length){
        chars[i] = null
        close.pop()
      }
    }
  }
  while(open.length > close.length){
    const curr = open.pop()
    chars[curr] = null
  }
  return chars.filter(ch => ch !== null).join("")
};

Boom. Another LeetCode solution.

Let's get started

Just let us know the basics and we'll send you a Slack invite to discuss with the whole team.

What are we going to be talking about?

%d bloggers like this: