Minimum number of parentheses to be removed to make a string of parentheses balanced

Question

The task:

Given a string of parentheses, write a function to compute the minimum number of parentheses to be removed to make the string valid (i.e. each open parenthesis is eventually closed).

For example, given the string "()())()", you should return 1. Given the string ")(", you should return 2, since we must remove all of them.

const brackets = "()())()";

My functional solution:

const numberOfUnbalanced = brackets => Object.values(brackets
  .split("")
  .reduce((brackCounter, b) => {
    b === "(" ? brackCounter.openBrackets++ :
    brackCounter.openBrackets ? brackCounter.openBrackets-- :
    brackCounter.closedBrackets++;

    return brackCounter;
  }, {openBrackets: 0, closedBrackets: 0}))
.reduce((sum, b) => sum + b, 0);

console.log(numberOfUnbalanced(brackets));

My imperative solution:

function numberOfUnbalanced2(brackets) {
  let openBrackets = 0, closedBrackets = 0;
  for (let i in brackets) {
    brackets[i] === "(" ? openBrackets++ :
    openBrackets ? openBrackets-- :
    closedBrackets++;
  }
  return openBrackets + closedBrackets;
}

console.log(numberOfUnbalanced2(brackets));

Usually the functional approach is shorter and tend to be easier to understand in comparison to imperative approaches. However, in this case it doesn't have any advantage to the imperative approach. I guess it is due to the nested structure in the functional solution.

Answer 1

for of not for in

I have noticed that on occasion you use the indexing for in Try to avoid using this loop as it can be problematic if the object you iterate has inherited properties not set as enumerable = false

Use the values iterator for of as it avoids the problems that come with for in. It also has the benefit of not needing to index the object for the value

Use const

When using either for of and for in and you don't intend to change the value or key use a const eg for(const i in brackets) or for(const char of brackets)

Note That you can not use a const in for(;;) loops but let is allowed. for(let i=0;i<10;i++). The reason is that even though a new instance of i is created each iteration and assigned the value of the previous i, the last loop expression i++ is applied at the bottom of the loop block and thus does not work for constants.

Simplify

Strings are iterable objects so you can avoid the need to use String.split and use the more succinct spread ... operator. eg [...string] is the same as string.split("");

Complexity

• Your imperative function is \$O(n)\$ time and \$O(1)\$ space.

• Your declarative (you call functional) function is \$O(n)\$ time and \$O(n)\$ space.

Ambiguity

The question does not indicate if the string will contain characters other than "()", yet the example shows only "()" and your solutions count characters other than "()" as ")" so will assume that the input string contains only "()"

Solutions

Imperative

function balanced(str) {
    var open = 0, closed = 0;
    for (const char of str) { char === "(" ? open++ : (open ? open-- : closed++) } 
    return open + closed ;
}

Declarative

function balanced(str) {
    const open = counts => (counts[0]++, counts);
    const close = counts => (counts[0] ? counts[0]-- : counts[1]++, counts);
    const counter = (counts, char) => char === "(" ? open(counts) : close(counts);
    const sum = arr => arr[0] + arr[1];
    const chars = str => [...str];
    return sum(chars(str).reduce(counter, [0, 0]));
}   

Functional

function balanced(str) {
    const counter = ([open, closed], char) => {
        char === "(" ? open++ : (open ? open-- : closed++);
        return [open, closed];
    }
    const sum = (sum, val) => sum += val;
    return [...str]
       .reduce(counter, [0, 0])
       .reduce(sum, 0);
}   

or

function balanced(str) {
    const counter = ([open, closed], char) =>
        (char === "(" ? open++ : (open ? open-- : closed++), [open, closed]);
    const res = [...str].reduce(counter, [0, 0])
    return res[0] + res[1];
}   

Answer 2

Nested ternaries tend to be hard to read. The writing style could help a lot though, consider this:

b === "("
  ? brackCounter.openBrackets++
  : brackCounter.openBrackets
    ? brackCounter.openBrackets--
    : brackCounter.closedBrackets++;

The term "bracket" is redundant within the implementation. What else would you count, have open or closed, than brackets? Nothing, so I suggest dropping that from the names:

• brackCounter -> counter
• openBrackets -> open
• closedBrackets -> closed

Functional programming tries to avoid mutation. The way the object {openBrackets: 0, closedBrackets: 0} is mutated through the reduce goes against that. You could return new tuples instead:

const numberOfUnbalanced = brackets => brackets
  .split("")
  .reduce(([open, closed], b) => {
    return b === "("
      ? [open + 1, closed]
      : open
        ? [open - 1, closed]
        : [open, closed + 1];
  }, [0, 0])
  .reduce((sum, b) => sum + b);