Invalid Parenthesis, by Google

Question was asked by Google (via Daily Coding Problem), here it is:

This problem was asked by Google.
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.

What can be done in linear time and O(1)-space is to keep track of a variable for the number of open brackets (since we're dealing with only one type of brackets, this solution should suffice). Whenever you find an open bracket, increment it. Whenever you find a closed bracket, if you don't have any open bracket yet, increment your error variable, otherwise decrement the open brackets by one.
At the end of the loop not only you have your errors, but you also have the remaining open brackets which are also errors, hence you add that up to the errors variable.
That's it!
Code is down below and on GitHub here: https://github.com/marcelodebarros/dailycodingproblem/blob/master/DailyCodingProblem12092018.cs

Thanks, Marcelo

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DailyCodingProblem
{
 class DailyCodingProblem12092018
 {
  public int BracketsMistakes(string brackets)
  {
   if (String.IsNullOrEmpty(brackets)) return 0;

   int errors = 0;
   int countOpen = 0;
   for (int i = 0; i < brackets.Length; i++)
   {
    if (brackets[i] == '(') countOpen++;
    else
     if (countOpen == 0) errors++;
     else countOpen--;
   }
   errors += countOpen;
   return errors;
  }
 }
}


Comments

Popular posts from this blog

Advent of Code - Day 6, 2024: BFS and FSM

Advent of Code - Day 7, 2024: Backtracking and Eval

Golang vs. C#: performance characteristics (simple case study)