CareerCup

Looking for coaching on interview preparation?
Visit AONECODE.COM for ONE-TO-ONE private lessons by FB, Google and Uber engineers!

System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. advanced algorithms and clean coding)
Interview questions sorted by companies
Mock Interviews

Ace G, U, FB, Amazon, LinkedIn, MS and other top-tier interviews in weeks of training.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

Solution: O(n)
first for-loop removes all invalid ')'. Second for-loop removes all invalid '('

public static String balanceParenthesis(String s) {
        StringBuilder str = new StringBuilder(s);
        int left = 0;
        for(int i = 0; i < str.length(); i++) {
            if(str.charAt(i) == '(') {
                left++;
            } else if(str.charAt(i) == ')') {
                if(left > 0) {
                    left--;
                } else {
                    str.deleteCharAt(i--);
                }
            }
        }
        int right = 0;
        for(int i = str.length() - 1; i >= 0; i--) {
            if(str.charAt(i) == ')') {
                right++;
            } else if(str.charAt(i) == '('){
                if(right > 0) right--;
                else {
                    str.deleteCharAt(i);
                }
            }
        }
        return str.toString();
    }

C#

public string LongestValidParenthese(string s)
{
int cnt = 0;
IList<int> open = new List<int>();
IList<int> close = new List<int>();
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '(')
{
cnt++;
open.Add(i);
}else if (s[i] == ')')
{
cnt--;
if (cnt < 0)
{
close.Add(i);
cnt = 0;
}
else
{
open.RemoveAt(open.Count - 1);
}
}
}
StringBuilder sb = new StringBuilder();
int lo = 0, lc = 0;
for (int i = 0; i < s.Length; i++)
{
if (s[i] == '(')
{
if (lo < open.Count && i == open[lo])
{
lo++;
}
else
{
sb.Append(s[i]);
}
}else if (s[i] == ')')
{
if (lc < close.Count && i == close[lc])
{
lc++;
}
else
{
sb.Append(s[i]);
}
}
else
{
sb.Append(s[i]);
}
}

return sb.ToString();
}

g

import java.util.ArrayList;
import java.util.List;

public class RemoveUnbalancedParenthesis {

	public static void main(String[] args) {
		String input = "i7difdk(ds()))98ijdskjf(89lk)8w(((()))))";
		System.out.println(removeUnbalancedParenthesis(input));
	}
	
	private static class PosAndLfRt{
		int pos;
		int ltRt;
		
		private PosAndLfRt(int pos, int ltRt){
			this.pos = pos;
			this.ltRt = ltRt;
		}
	}
	
	public static String removeUnbalancedParenthesis(String input){
		StringBuilder str = new StringBuilder(input);
		List<PosAndLfRt> parenthesis = new ArrayList<>();
		for(int i=0;i<str.length();i++){
			char charecter = str.charAt(i);
			if(charecter == '('){
				parenthesis.add(new PosAndLfRt(i,1));
			}else if(charecter == ')'){
				parenthesis.add(new PosAndLfRt(i,-1));
			}
		}
		int track = 0;
		List<Integer> posToRemove = new ArrayList<>();
		for (PosAndLfRt posAndLfRt : parenthesis) {
			track += posAndLfRt.ltRt;
			if(track<0){
				posToRemove.add(posAndLfRt.pos);
				track++;
			}
		}
		int posToRmvLen = posToRemove.size();
		for (int i = posToRmvLen-1;i>=0;i--) {
			str.deleteCharAt(posToRemove.get(i));
		}
		return str.toString();
	}
}

import scala.collection.immutable.Stack

object BalanceParenthesis extends App {

  println(balance("((a((aa(((()d(())("))

  def balance(input: String): String = {
    var stack = Stack.empty[Int]
    var remove = Set.empty[Int]
    val withIndices = input.toCharArray.zipWithIndex

    withIndices.foreach { case (c, i) =>
      c match {
        case '(' => stack = stack.push(i)
        case ')' => if (stack.isEmpty) remove = remove + i else stack = stack.pop
        case _ =>
      }
    }

    remove = remove ++ stack.toSet
    withIndices.filterNot(v => remove.contains(v._2)).map(_._1).mkString
  }

}

1-5-(8+9)+6)

I did something similar to the scala one..
1. loop through the entire string
1.a. if ( is found push it in stack
1.b.i if ) is found pop it from stack
1.b.ii if ) is found and there is no matching ( <empty stack> then remove )
2 at the end stack has all the ( with no matching ) and so remove all ( in the stack

import java.io.IOException;
import java.util.EmptyStackException;
import java.util.Scanner;
import java.util.Stack;

public class Solution1a
{

    private static final Scanner in = new Scanner(System.in);
    private static String input;

    public static void main(String[] args) throws IOException
    {
        input = in.nextLine();
        balPara();
        System.out.println(input);
    }

    private static void balPara()
    {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < input.length(); i++)
            if (input.charAt(i) == '(')
                stack.push(i);
            else if (input.charAt(i) == ')')
                try {
                    stack.pop();
                }
                catch (EmptyStackException e) {
                    input = input.substring(0, i) + input.substring(i + 1);
                    i--;
                }
        while (stack.size() > 0) {
            input = input.substring(0, stack.peek()) + input.substring(stack.peek() + 1);
            stack.pop();
        }
    }

}

You mind adding some example to the question?

static void trim(char[] chars){
  
    if(chars == null)
      throw new IllegalArgumentException();
      
    Stack<Character> s = new Stack<>();
      
    int i=0;
  
    for(;i<chars.length; i++){
    
         if(chars[i] == '(')
            s.push('(');
         else{
            if(!s.isEmpty() && s.peek().equals('(')){
                if(chars[i] == ')')
                    s.pop();
            }
            else{
                chars[i] = '#';
            }
         }    
    }
  
    int j = i-1;
  
    while(!s.isEmpty()){
      
        char c = chars[j];
        chars[j] = '#';
    
        if(c == '(')
            s.pop();
    }
  
  }

public static String balanceParentesis(String string){
		
		StringBuffer sb = new StringBuffer(string);
		
		int noOfParenthesis = 0;
		for(int x = 0; x < string.length(); x ++){
			if(string.charAt(x) == '(' || string.charAt(x) == ')')
				noOfParenthesis++;
		}
		
		int noOfOtherCharts = string.length() - noOfParenthesis;
		int elementsToDelete = noOfOtherCharts - noOfParenthesis;
		
		boolean flag = (elementsToDelete == 0) ? false : true;
		int x = 0;
		int deletedItems = 0;
		while(flag){
			
			boolean resultFinding = (elementsToDelete < 0)? 
					(string.charAt(x) != ')' && string.charAt(x) != '(') 
						: string.charAt(x) == ')' || string.charAt(x) == '(';
			
			if(resultFinding){
				sb.deleteCharAt(x);
				string = sb.toString();
				deletedItems++;
				if(deletedItems == elementsToDelete)
					flag = false;
			}else{
				x++;
			}
		}
		
		return sb.toString();
		
	}

function balanceParenthesis(str) {
	let arr = []
	return str.split('').reduce((a,e) => {
		if(e === '(') {
			arr.push('(');
		} else if(e === ')') {
			if(arr.length > 0) {
				arr.pop();
			} else {
				return a;
			}
		}
		return a+e;
	},'')
}

import java.util.Arrays;
import java.util.Stack;

public class MinDeletionsToBalanceParantheses {
	public static void main(String[] args){
		String[] testcase = { "()())()" , "((a((aa((()d(())(",
			"())))()(((()))))))()(((()(()))("
		};
		
		for (String test : testcase){
			String res = balance(test);
			System.out.println(test + " result: " + res);	
		}
   }
   
   public static String balance(String inp) {
	   Stack<Integer> stack = new Stack<Integer>();
	   int n = inp.length();
	   char[] inpc = inp.toCharArray();
	   boolean[] markedForDeletion = new boolean[n];
	   Arrays.fill(markedForDeletion, false);
	   for (int i = 0; i < n; i++) {
		   char c = inpc[i];
		   if (c == ')') {
			   if (stack.isEmpty()) {
				   markedForDeletion[i] = true;
			   } else {
				   stack.pop();
			   }
		   } else if(c == '('){
			   stack.push(i);
		   }
	   }
	   
	   while(!stack.isEmpty()){
		   markedForDeletion[stack.pop()] = true;
	   }
	   
	   int numDeletions = 0;
	   String res = "";
	   for (int i = 0; i < n; i++){
		   if (!markedForDeletion[i]){
			   res = res + inpc[i];
		   } else {
			   numDeletions++;
		   }
	   }
	   System.out.println("numDeletions " + numDeletions);
	   return res;
   }
}

balance("()") -> "()"
balance("a(b)c)") -> "a(b)c"
balance(")(") -> ""
balance("(((((") -> ""
balance("(()()(") -> "()()"
balance(")(())(") -> "(())"
balance(")())(()()(") -> "()()()"

There can be multiple correct results per input:
balance("(())())") -> "(()())" or "(())()"