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
-
Initialize
track
to keep track of the difference between the number of opening and closing parentheses. Initializeresult
to store the total cost andcount
array to keep track of the number of unbalanced parentheses at each position. -
Traverse the
text
character by character. When you encounter an opening parenthesis, incrementtrack
, and when you encounter a closing parenthesis, decrementtrack
. -
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 oftrack
, and you add this value to theresult
. -
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).
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.
New Comment