_1249.java

packagecom.fishercoder.solutions.secondthousand;

importjava.util.Deque;
importjava.util.LinkedList;

publicclass_1249 {
publicstaticclassSolution1 {
publicStringminRemoveToMakeValid(Strings) {
Deque<Character> stack = newLinkedList<>();
intleftParen = 0;
intrightParen = 0;
for (charc : s.toCharArray()) {
if (c == '(') {
stack.push(c);
leftParen++;
 } elseif (c == ')') {
if (leftParen > rightParen) {
stack.push(c);
rightParen++;
 }
 } else {
stack.push(c);
 }
 }
StringBuildersb = newStringBuilder();
intdiff = leftParen - rightParen;
while (!stack.isEmpty()) {
if (stack.peek() == '(') {
if (diff-- > 0) {
stack.pop();
 } else {
sb.append(stack.pop());
 }
 } else {
sb.append(stack.pop());
 }
 }
returnsb.reverse().toString();
 }
 }

publicstaticclassSolution2 {
/*
 * My completely original solution on 10/26/2021.
 */
publicStringminRemoveToMakeValid(Strings) {
Deque<String> stack = newLinkedList<>();
intleft = 0;
intright = 0;
for (charc : s.toCharArray()) {
if (c == '(') {
stack.addLast(c + "");
left++;
 } elseif (c == ')') {
if (left <= right) {
continue;
 } else {
right++;
stack.addLast(c + "");
 }
 } else {
stack.addLast(c + "");
 }
 }
left = 0;
right = 0;
StringBuildersb = newStringBuilder();
while (!stack.isEmpty()) {
Stringstr = stack.pollLast();
if (str.equals(")")) {
right++;
sb.append(str);
 } elseif (str.equals("(")) {
if (right > left) {
sb.append(str);
left++;
 }
 } else {
sb.append(str);
 }
 }
returnsb.reverse().toString();
 }
 }
}