Posted on by Kalkicode
Code Greedy

# 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.

## 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).

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post