CodingGyan

Minimum Additions for Valid Parentheses

medium Strings

Problem

The word has only ( and ). In one move you may insert a bracket at any place. Print the smallest number of insertions that makes the word a valid bracket string (every bracket matched, in the right order).

Constraints

  • 1 <= length <= 10^5
  • only ( and )

Examples

Input

())

Output

1

Solutions

Best approachTime O(n)Space O(1)

Only the number of waiting ( matters, so a counter replaces the stack. A ) with nothing waiting needs one inserted (. At the end each waiting ( needs one inserted ). O(n) time, O(1) memory.

Same code works in Java810172125Basic features only, so nothing changes between versions.
/*
 * Problem : Fix brackets.
 * Input   : One bracket word.
 * Output  : Insert count.
 * Approach: Counter.
 * Time    : O(n)
 * Space   : O(1)
 * Java    : 8 or newer.
 */
import java.util.Scanner;

public class Main {
    // This method solves the task. It receives the input and returns the answer.
    static int solve(String s) {
        // Step 1: "open" counts ( that wait for a ). "added" counts the ( we must add for a ) with nothing to match.
        int open = 0;
        int added = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                open++;
            } else if (open > 0) {
                open--;
            } else {
                added++;
            }
        }
        // Step 2: Each ( still waiting needs one more ).
        return open + added;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.hasNextLine() ? scanner.nextLine() : "";
        System.out.println(solve(s));
    }
}
Hints (2)
  1. What do we do for a ) when open is 0?
  2. What is left at the end?