Count cost to balance the parentheses

The problem are counting the cost required to balance parentheses in a given text. Unbalanced parentheses occur when there's a mismatch between opening '(' and closing ')' parentheses. The task is to move characters within the text to balance the parentheses and calculate the total cost of these moves.

Problem Description

The problem involves taking a string as input, where the string contains only parentheses, and determining the minimum cost required to balance the parentheses. The cost is incurred when characters are moved to achieve the balance. Each move involves taking a character from one position and placing it in another.

Example

Let's break down one of the examples you've given to illustrate the problem-solving approach:

Text: (())))(()(

In this example, you start with an unbalanced text where the opening and closing parentheses are mismatched. Your goal is to minimize the cost by moving characters around to achieve balanced parentheses.

    text = (())))(()(
        ────────────────────────

            (()) ))(()(
                │  │
                └──┘         ①
                cost 2

        Move character at 6th to 4th position

            (()) ))(()(  
                  ││   first move
                  └┘  
            (()) )()()(   After move
                 ││   second move
                 └┘      
            (()) ())()( <- After move
        ──────────────────────── 
            
            (())() )()(
                  │   │      ②
                  └───┘ 
                  cost 3

            (())() )()(
                     ││   first move
                     └┘    
            (())() )(()
                    ││   second move
                    └┘    
            (())() )(()
                   ││    Third move
                   └┘  
            (())() ()()

        Move character at 9th to 6th position
        ──────────────────────── 

        Total cost : (2 + 3) = 5

Idea to Solve

To solve this problem, you need to analyze the text and come up with a strategy to balance the parentheses while minimizing the cost. One approach is to keep track of the number of unbalanced parentheses as you traverse the text. When you encounter a closing parenthesis without a corresponding opening parenthesis, you'll need to move a character to the left to balance it. Similarly, if you encounter an opening parenthesis without a corresponding closing parenthesis, you'll need to move a character to the right.

Pseudocode

function getCost(text: string) -> int:
    n = length(text)
    if n is 0:
        return -1
    
    track = 0
    result = 0
    count = array of size n
    
    for i from 0 to n - 1:
        if text[i] is '(':
            increment track
        else:
            decrement track
        
        if track < 0:
            result += absolute value of track
    
    return result

Algorithm Explanation

1. Initialize track to keep track of the difference between the number of opening and closing parentheses. Initialize result to store the total cost and count array to keep track of the number of unbalanced parentheses at each position.

2. Traverse the text character by character. When you encounter an opening parenthesis, increment track, and when you encounter a closing parenthesis, decrement track.

3. If at any point track becomes negative, it means there are more closing parentheses than opening parentheses before this position. This is an unbalanced state, and you need to move characters to balance it. The number of characters to move is the absolute value of track, and you add this value to the result.

4. Finally, return the result as the total cost.

Code Solution

1) Cost to balance the parentheses in java 2) Cost to balance the parentheses in c++ 3) Cost to balance the parentheses in c 4) Cost to balance the parentheses in c# 5) Cost to balance the parentheses in php 6) Cost to balance the parentheses in python 7) Cost to balance the parentheses in ruby 8) Cost to balance the parentheses in scala 9) Cost to balance the parentheses in swift 10) Cost to balance the parentheses in kotlin 11) Cost to balance the parentheses in vb.net 12) Cost to balance the parentheses in golang 13) Cost to balance the parentheses in node js

Time Complexity

The algorithm traverses the input text once, which takes O(n) time, where n is the length of the input text. The operations inside the loop (incrementing, decrementing, and array updates) are constant time operations. Therefore, the overall time complexity of the algorithm is O(n).