Given a string str consisting of characters ‘(‘, ‘)’, ‘[‘, ‘]’, ‘{‘ and ‘}’ only. The task is to find the maximum length of the balanced string after removing any character and swapping any two adjacent characters.
Examples:
Input: str = “))[]]((”
Output: 6
The string can be converted to ()[]()
Input: str = “{{{{{{{}”
Output: 2
Approach: The idea is to remove extra unmatched parentheses from the string because we cannot generate a balanced pair for it and swap the remaining characters to balance the string. Therefore the answer is the equal summation of pairs of all balanced parenthesis. Note that we can move a character to any other place by adjacent swappings.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the length of// the longest balanced sub-stringint maxBalancedStr(string s){ // To store the count of parentheses int open1 = 0, close1 = 0; int open2 = 0, close2 = 0; int open3 = 0, close3 = 0; // Traversing the string for (int i = 0; i < s.length(); i++) { // Check type of parentheses and // incrementing count for it switch (s[i]) { case '(': open1++; break; case ')': close1++; break; case '{': open2++; break; case '}': close2++; break; case '[': open3++; break; case ']': close3++; break; } } // Sum all pair of balanced parentheses int maxLen = 2 * min(open1, close1) + 2 * min(open2, close2) + 2 * min(open3, close3); return maxLen;}// Driven codeint main(){ string s = "))[]](("; cout << maxBalancedStr(s); return 0;} |
Java
// Java implementation of the approachclass GFG{ // Function to return the length of// the longest balanced sub-stringstatic int maxBalancedStr(String s){ // To store the count of parentheses int open1 = 0, close1 = 0; int open2 = 0, close2 = 0; int open3 = 0, close3 = 0; // Traversing the string for (int i = 0; i < s.length(); i++) { // Check type of parentheses and // incrementing count for it switch (s.charAt(i)) { case '(': open1++; break; case ')': close1++; break; case '{': open2++; break; case '}': close2++; break; case '[': open3++; break; case ']': close3++; break; } } // Sum all pair of balanced parentheses int maxLen = 2 * Math.min(open1, close1) + 2 * Math.min(open2, close2) + 2 * Math.min(open3, close3); return maxLen;}// Driven codepublic static void main(String[] args){ String s = "))[]](("; System.out.println(maxBalancedStr(s));}}// This code is contributed by Code_Mech. |
Python3
# Python 3 implementation of the approach# Function to return the length of# the longest balanced sub-stringdef maxBalancedStr(s): # To store the count of parentheses open1 = 0 close1 = 0 open2 = 0 close2 = 0 open3 = 0 close3 = 0 # Traversing the string for i in range(len(s)): # Check type of parentheses and # incrementing count for it if(s[i] == '('): open1 += 1 continue if s[i] == ')': close1 += 1 continue if s[i] == '{': open2 += 1 continue if s[i] == '}': close2 += 1 continue if s[i] == '[': open3 += 1 continue if s[i] == ']': close3 += 1 continue # Sum all pair of balanced parentheses maxLen = (2 * min(open1, close1) + 2 * min(open2, close2) + 2 * min(open3, close3)) return maxLen# Driven codeif __name__ == '__main__': s = "))[]]((" print(maxBalancedStr(s))# This code is contributed by# Surendra_Gangwar |
C#
// C# implementation of the approachusing System;class GFG{ // Function to return the length of// the longest balanced sub-stringstatic int maxBalancedStr(string s){ // To store the count of parentheses int open1 = 0, close1 = 0; int open2 = 0, close2 = 0; int open3 = 0, close3 = 0; // Traversing the string for (int i = 0; i < s.Length; i++) { // Check type of parentheses and // incrementing count for it switch (s[i]) { case '(': open1++; break; case ')': close1++; break; case '{': open2++; break; case '}': close2++; break; case '[': open3++; break; case ']': close3++; break; } } // Sum all pair of balanced parentheses int maxLen = 2 * Math.Min(open1, close1) + 2 * Math.Min(open2, close2) + 2 * Math.Min(open3, close3); return maxLen;}// Driver codepublic static void Main(){ string s = "))[]](("; Console.WriteLine(maxBalancedStr(s));}}// This code is contributed by Code_Mech. |
PHP
<?php// PHP implementation of the approach// Function to return the length of// the longest balanced sub-string function maxBalancedStr($s){ // To store the count of parentheses $open1 = 0; $close1 = 0; $open2 = 0; $close2 = 0; $open3 = 0; $close3 = 0; // Traversing the string for ($i = 0; $i < strlen($s); $i++) { // Check type of parentheses and // incrementing count for it switch ($s[$i]) { case '(': $open1++; break; case ')': $close1++; break; case '{': $open2++; break; case '}': $close2++; break; case '[': $open3++; break; case ']': $close3++; break; } } // Sum all pair of balanced parentheses $maxLen = 2 * min($open1, $close1) + 2 * min($open2, $close2) + 2 * min($open3, $close3); return $maxLen;}// Driven code{ $s = "))[]](("; echo(maxBalancedStr($s));}// This code is contributed by Code_Mech. |
Javascript
<script>// Javascript implementation of the approach // Function to return the length of // the longest balanced sub-string function maxBalancedStr( s) { // To store the count of parentheses var open1 = 0, close1 = 0; var open2 = 0, close2 = 0; var open3 = 0, close3 = 0; // Traversing the string for (i = 0; i < s.length; i++) { // Check type of parentheses and // incrementing count for it switch (s.charAt(i)) { case '(': open1++; break; case ')': close1++; break; case '{': open2++; break; case '}': close2++; break; case '[': open3++; break; case ']': close3++; break; } } // Sum all pair of balanced parentheses var maxLen = 2 * Math.min(open1, close1) + 2 * Math.min(open2, close2) + 2 * Math.min(open3, close3); return maxLen; } // Driven code var s = "))[]](("; document.write(maxBalancedStr(s));// This code contributed by gauravrajput1</script> |
Output
6
Time Complexity: O(n), where n is the length of the given string.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!