Minimize cost to rearrange substrings to convert a string to a Balanced Bracket Sequence
Given a string S of length N consisting of characters β(β and β)β only, the task is to convert the given string into a balanced parenthesis sequence by selecting any substring from the given string S and reorder the characters of that substring. Considering length of each substring to be the cost of each operation, minimize the total cost required.
A string is called balanced if every opening parenthesis β(β has a corresponding closing parenthesis β)β.
Examples:
Input: str = β)(()β
Output: 2
Explanation:
Choose substring S[0, 1] ( = β)(β ) and rearrange it to β()β. Cost = 2.
Now, the string modifies to S = β()()β, which is balanced.Input: S = β()))β
Output: -1
Approach: The idea is to first check if the string can be balanced or not i.e., count the number of open and closed parenthesis and if they are unequal, then print -1. Otherwise, follow the steps below to find the total minimum cost:
- Initialize an array arr[] of length N.
- Initialize sum as 0 to update the array elements with the values sum.
- Traverse the given string from i = 0 to N β 1 and perform the following steps:
- If the current character is β(β, then update arr[i] as (sum + 1). Otherwise, update arr[i] as (sum β 1).
- Update the value of sum as arr[i].
- After completing the above steps, if the value of arr[N β 1] is non-zero then string canβt be balanced and print β-1β.
- If the string can be balanced, then print the sum of sizes of disjoint subarray having sum 0 as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to count minimum number of // operations to convert the string to // a balanced bracket sequence void countMinMoves(string str) { int n = str.size(); // Initialize the integer array int a[n] = { 0 }; int j, ans = 0, i, sum = 0; // Traverse the string for (i = 0; i < n; i++) { // Decrement a[i] if (str[i] == ')' ) { a[i] += sum - 1; } // Increment a[i] else { a[i] += sum + 1; } // Update the sum as current // value of arr[i] sum = a[i]; } // If answer exists if (sum == 0) { // Traverse from i i = 1; // Find all substrings with 0 sum while (i < n) { j = i - 1; while (i < n && a[i] != 0) i++; if (i < n && a[i - 1] < 0) { ans += i - j; if (j == 0) ans++; } i++; } // Print the sum of sizes cout << ans << endl; } // No answer exists else cout << "-1\n" ; } // Driver Code int main() { string str = ")(()" ; countMinMoves(str); return 0; } |
Java
// Java program for the above approach class GFG { // Function to count minimum number of // operations to convert the string to // a balanced bracket sequence static void countMinMoves(String str) { int n = str.length(); // Initialize the integer array int a[] = new int [n]; int j, ans = 0 , i, sum = 0 ; // Traverse the string for (i = 0 ; i < n; i++) { // Decrement a[i] if (str.charAt(i) == ')' ) { a[i] += sum - 1 ; } // Increment a[i] else { a[i] += sum + 1 ; } // Update the sum as current // value of arr[i] sum = a[i]; } // If answer exists if (sum == 0 ) { // Traverse from i i = 1 ; // Find all substrings with 0 sum while (i < n) { j = i - 1 ; while (i < n && a[i] != 0 ) i++; if (i < n && a[i - 1 ] < 0 ) { ans += i - j; if (j == 0 ) ans++; } i++; } // Print the sum of sizes System.out.println(ans); } // No answer exists else System.out.println( "-1" ); } // Driver Code public static void main(String[] args) { String str = ")(()" ; countMinMoves(str); } } // This code is contributed by AnkThon |
Python3
# Python3 program for the above approach # Function to count minimum number of # operations to convert the string to # a balanced bracket sequence def countMinMoves( str ): n = len ( str ) # Initialize the integer array a = [ 0 for i in range (n)] j, ans, sum = 0 , 0 , 0 # Traverse the string for i in range (n): # Decrement a[i] if ( str [i] = = ')' ): a[i] + = sum - 1 # Increment a[i] else : a[i] + = sum + 1 # Update the sum as current # value of arr[i] sum = a[i] # If answer exists if ( sum = = 0 ): # Traverse from i i = 1 # Find all substrings with 0 sum while (i < n): j = i - 1 while (i < n and a[i] ! = 0 ): i + = 1 if (i < n and a[i - 1 ] < 0 ): ans + = i - j if (j = = 0 ): ans + = 1 i + = 1 # Print the sum of sizes print (ans) # No answer exists else : print ( "-1" ) # Driver Code if __name__ = = '__main__' : str = ")(()" countMinMoves( str ) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; class GFG { // Function to count minimum number of // operations to convert the string to // a balanced bracket sequence static void countMinMoves( string str) { int n = str.Length; // Initialize the integer array int []a = new int [n]; int j, ans = 0, i, sum = 0; // Traverse the string for (i = 0; i < n; i++) { // Decrement a[i] if (str[i] == ')' ) { a[i] += sum - 1; } // Increment a[i] else { a[i] += sum + 1; } // Update the sum as current // value of arr[i] sum = a[i]; } // If answer exists if (sum == 0) { // Traverse from i i = 1; // Find all substrings with 0 sum while (i < n) { j = i - 1; while (i < n && a[i] != 0) i++; if (i < n && a[i - 1] < 0) { ans += i - j; if (j == 0) ans++; } i++; } // Print the sum of sizes Console.WriteLine(ans); } // No answer exists else Console.WriteLine( "-1" ); } // Driver Code public static void Main() { string str = ")(()" ; countMinMoves(str); } } // This code is contributed by bgangwar59 |
Javascript
<script> // JavaScript program for the above approach // Function to count minimum number of // operations to convert the string to // a balanced bracket sequence function countMinMoves(str) { var n = str.length; // Initialize the integer array var a = Array(n).fill(0); var j, ans = 0, i, sum = 0; // Traverse the string for (i = 0; i < n; i++) { // Decrement a[i] if (str[i] == ')' ) { a[i] += sum - 1; } // Increment a[i] else { a[i] += sum + 1; } // Update the sum as current // value of arr[i] sum = a[i]; } // If answer exists if (sum == 0) { // Traverse from i i = 1; // Find all substrings with 0 sum while (i < n) { j = i - 1; while (i < n && a[i] != 0) i++; if (i < n && a[i - 1] < 0) { ans += i - j; if (j == 0) ans++; } i++; } // Print the sum of sizes document.write( ans + "<br>" ); } // No answer exists else document.write( "-1<br>" ); } // Driver Code var str = ")(()" ; countMinMoves(str); </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)
Contact Us