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.
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.
Let's break down one of the examples you've given to illustrate the problem-solving approach:
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.
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
trackto keep track of the difference between the number of opening and closing parentheses. Initialize
resultto store the total cost and
countarray to keep track of the number of unbalanced parentheses at each position.
textcharacter by character. When you encounter an opening parenthesis, increment
track, and when you encounter a closing parenthesis, decrement
If at any point
trackbecomes 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
Finally, return the
resultas the total cost.
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
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).