All we need to do is to delete unnecessary parenthesis. every time we encounter a ')' which has no previous '(' to match with, delete. delete every '(' left when we finished reading the string s.

string justify(string str) { string s1 = ""; int l = 0, i; for(i = 0; i 0) { l --; s1 += ')'; } else if(str[i] == '(') { s1 += '('; l++; } } for(i = 0; i < l; i++) s1 += ')'; return s1; }

@xemoaya try print balanceParanthesis(")))((("): you solution is wrong!! --> ((()))((())) @hussein try cout ((()))

well according to the given examples, this code would do good void balance(char *u) { int n=strlen(u); int i=n-1; //modified string length for(;i>=0;--i) { if(u[i]=='(') --n; else break; } //remove extra right braces int l=0; for(int i=0;i

one small change needed for(;l>0;--l,pos++) { output[pos]=')'; } output[pos]='\0'; need to add extra ) at end

how about simple balancing with an open count? close any that are unclosed. but before that run a round to delete leading ')' and trailing '(' which are be deemed unnecessary.

well in the above code for(;i>=0;--i) { if(u[i]=='(') --n; else break; } part removes trailing '(' then ofcourse we are removing and extra ')' [ones not balanced by a '('] finally if there were more {remember that by our approach we can never have more ')'} '(' then we need to balance them with ')' that is what this part of the code does for(;l>0;--l,pos++) { output[pos]=')'; } output[pos]='\0'; this part compacts the string, so we can do convert it inplace, if a standard technique to delete certain parts of a string is to fill those parts with '\0' and then compact the string that is what this does int pos=0; for(int i=0;i

Use O(n) time and O(1) space.

import java.util.*; class BalanceParanthesis { static String getBalancedHelper(String input) { int count=0; for(int i=0;i0) //'(' is extra { while(input.charAt(0)=='('&& count!=0) { input=input.substring(1,input.length()); count--; if(input.length()==0) break; } while(count!=0) { input+=")"; count--; } } else if(count0) if(input.charAt(0)=='('&&input.charAt(input.length()-1)==')') input=input.substring(1,input.length()-1); return input; } static String getBalanced(String input) { Stack chars=new Stack(); Stack index=new Stack(); for(int i=0;i0) { System.out.println("in partition"); return getBalancedHelper(input.substring(0,ind+1))+getBalancedHelper(input.substring(ind+1,input.length())); } } return getBalancedHelper(input); } public static void main(String[] st) { String input=")))((("; System.out.print(input+" result: "+getBalanced(input)); } }

def removeExtra(s,op,cl): count = 0 out = '' for c in s: if c == op: count += 1 out += c elif c == cl: if count > 0: count -= 1 out += c else: out += c return out def parenBalance(s): return removeExtra(removeExtra(s,'(',')')[::-1], ')', '(')[::-1]

No I think the correct form of ")))(((" is not "((()))" since you are not allowed to change the ordering of elements. You change the ordering of original parenthesis. Even though you can change the ordering the difference between ((())) and )))((( is still 6.

Actually I think there is some mistake in the question itself. If the solution persue minimum difference, ")))(((" should lead to "((()))" since the difference between the input and output is 0. However, in the question ")))((("'s output is "", then the difference is 6.