Given a string str, the task is to find the maximum count of pairs (str[i], str[j]) of balanced parenthesis required to be removed such that the string does not contain any subsequence of balanced parenthesis:
Examples:
Input: str = “{(})”
Output: 2
Explanation:
Removing the pair of valid parenthesis(0, 2) modified str to “()”
Removing the pair of valid parenthesis(0, 1) modified str to “”.
Now, str does not contain any valid parenthesis. The required output is 2.Input: str = “)}(}”
Output: 0
Approach: The problem can be solved using Greedy technique. Follow the steps below to solve the problem:
- Initialize three variables, say cntSqr, cntCurly and cntSml, to store the count of “[” valid parenthesis, count of “{}”valid parenthesis and count of small valid parenthesis respectively.
- Initialize a variable, say cntPairs, to store the count of pairs of balanced parenthesis required to be removed such that the string does not contain any subsequence of balanced parenthesis.
- Iterate over the characters of string and check for the following conditions:
- If str[i] == ‘(‘, then increment the value of cntSml by 1.
- If str[i] = ‘{‘, then increment the value of cntCurly by 1.
- If str[i] = ‘[‘, then increment the value of cntSqr by 1.
- If str[i] = ‘]’, then check if cntSqr greater than 0 or not. If found to be true, then decrement the value of cntSqr by 1 and increment the value of cntPairs by 1.
- If str[i] = ‘}’, then check if cntCurly greater than 0 or not. If found to be true, then decrement the value of cntCurly by 1 and increment the value of cntPairs by 1.
- If str[i] = ‘)’, then check if cntSml greater than 0 or not. If found to be true, then decrement the value of cntSml by 1 and increment the value of cntPairs by 1.
- Finally, print the value of cntPairs.
Below is the implementation for the above approach:
C++
// C++ program to implement// the above approach#include <iostream>using namespace std;// Function to find the maximum count of pairs// required to be removed such that subsequence// of string does not contain any valid parenthesisvoid cntBalancedParenthesis(string s, int N){ // Stores count of pairs // of balanced parenthesis int cntPairs = 0; // Stores count of curly // balanced parenthesis int cntCurly = 0; // Stores count of small // balanced parenthesis int cntSml = 0; // Stores count of square // balanced parenthesis int cntSqr = 0; // Iterate over characters // of the string for (int i = 0; i < N; i++) { if (s[i] == '{') { // Update cntCurly cntCurly++; } else if (s[i] == '(') { // Update cntSml cntSml++; } else if (s[i] == '[') { // Update cntSqr cntSqr++; } else if (s[i] == '}' && cntCurly > 0) { // Update cntCurly cntCurly--; // Update cntPairs cntPairs++; } else if (s[i] == ')' && cntSml > 0) { // Update cntSml cntSml--; // Update cntPairs cntPairs++; } else if (s[i] == ']' && cntSqr > 0) { // Update cntSml cntSqr--; // Update cntPairs cntPairs++; } } cout << cntPairs;}// Driver Codeint main(){ // Given String string s = "{(})"; int N = s.length(); // Function call cntBalancedParenthesis(s, N); return 0;} |
Java
// Java program to implement// the above approachimport java.io.*;class GFG { // Function to find the maximum count of pairs // required to be removed such that subsequence // of string does not contain any valid parenthesis static void cntBalancedParenthesis(String s, int N) { // Stores count of pairs // of balanced parenthesis int cntPairs = 0; // Stores count of curly // balanced parenthesis int cntCurly = 0; // Stores count of small // balanced parenthesis int cntSml = 0; // Stores count of square // balanced parenthesis int cntSqr = 0; // Iterate over characters // of the string for (int i = 0; i < N; i++) { if (s.charAt(i) == '{') { // Update cntCurly cntCurly++; } else if (s.charAt(i) == '(') { // Update cntSml cntSml++; } else if (s.charAt(i) == '[') { // Update cntSqr cntSqr++; } else if (s.charAt(i) == '}' && cntCurly > 0) { // Update cntCurly cntCurly--; // Update cntPairs cntPairs++; } else if (s.charAt(i) == ')' && cntSml > 0) { // Update cntSml cntSml--; // Update cntPairs cntPairs++; } else if (s.charAt(i) == ']' && cntSqr > 0) { // Update cntSml cntSqr--; // Update cntPairs cntPairs++; } } System.out.println(cntPairs); } // Driver Code public static void main(String[] args) { // Given String String s = "{(})"; int N = s.length(); // Function call cntBalancedParenthesis(s, N); }}// This code is contributed by Dharanendra L V |
Python3
# Python program to implement# the above approach# Function to find the maximum count of pairs# required to be removed such that subsequence# of string does not contain any valid parenthesisdef cntBalancedParenthesis(s, N): # Stores count of pairs # of balanced parenthesis cntPairs = 0; # Stores count of curly # balanced parenthesis cntCurly = 0; # Stores count of small # balanced parenthesis cntSml = 0; # Stores count of square # balanced parenthesis cntSqr = 0; # Iterate over characters # of the string for i in range(N): if (ord(s[i]) == ord('{')): # Update cntCurly cntCurly += 1; elif (ord(s[i]) == ord('(')): # Update cntSml cntSml += 1; elif (ord(s[i]) == ord('[')): # Update cntSqr cntSqr += 1; elif (ord(s[i]) == ord('}') and cntCurly > 0): # Update cntCurly cntCurly -=1; # Update cntPairs cntPairs += 1; elif (ord(s[i]) == ord(')') and cntSml > 0): # Update cntSml cntSml -=1; # Update cntPairs cntPairs += 1; elif (ord(s[i]) == ord(']') and cntSqr > 0): # Update cntSml cntSqr -=1; # Update cntPairs cntPairs += 1; print(cntPairs);# Driver Codeif __name__ == '__main__': # Given String s = "{(})"; N = len(s); # Function call cntBalancedParenthesis(s, N);# This code is contributed by 29AjayKumar |
C#
// C# program to implement// the above approachusing System;class GFG { // Function to find the maximum count of pairs // required to be removed such that subsequence // of string does not contain any valid parenthesis static void cntBalancedParenthesis(String s, int N) { // Stores count of pairs // of balanced parenthesis int cntPairs = 0; // Stores count of curly // balanced parenthesis int cntCurly = 0; // Stores count of small // balanced parenthesis int cntSml = 0; // Stores count of square // balanced parenthesis int cntSqr = 0; // Iterate over characters // of the string for (int i = 0; i < N; i++) { if (s[i] == '{') { // Update cntCurly cntCurly++; } else if (s[i] == '(') { // Update cntSml cntSml++; } else if (s[i] == '[') { // Update cntSqr cntSqr++; } else if (s[i] == '}' && cntCurly > 0) { // Update cntCurly cntCurly--; // Update cntPairs cntPairs++; } else if (s[i] == ')' && cntSml > 0) { // Update cntSml cntSml--; // Update cntPairs cntPairs++; } else if (s[i] == ']' && cntSqr > 0) { // Update cntSml cntSqr--; // Update cntPairs cntPairs++; } } Console.WriteLine(cntPairs); } // Driver Code static public void Main() { // Given String String s = "{(})"; int N = s.Length; // Function call cntBalancedParenthesis(s, N); }}// This code is contributed by Dharanendra L V |
Javascript
<script>// Javascript program to implement// the above approach // Function to find the maximum count of pairs // required to be removed such that subsequence // of string does not contain any valid parenthesis function cntBalancedParenthesis( s , N) { // Stores count of pairs // of balanced parenthesis var cntPairs = 0; // Stores count of curly // balanced parenthesis var cntCurly = 0; // Stores count of small // balanced parenthesis var cntSml = 0; // Stores count of square // balanced parenthesis var cntSqr = 0; // Iterate over characters // of the string for (i = 0; i < N; i++) { if (s.charAt(i) == '{') { // Update cntCurly cntCurly++; } else if (s.charAt(i) == '(') { // Update cntSml cntSml++; } else if (s.charAt(i) == '[') { // Update cntSqr cntSqr++; } else if (s.charAt(i) == '}' && cntCurly > 0) { // Update cntCurly cntCurly--; // Update cntPairs cntPairs++; } else if (s.charAt(i) == ')' && cntSml > 0) { // Update cntSml cntSml--; // Update cntPairs cntPairs++; } else if (s.charAt(i) == ']' && cntSqr > 0) { // Update cntSml cntSqr--; // Update cntPairs cntPairs++; } } document.write(cntPairs); } // Driver Code // Given String var s = "{(})"; var N = s.length; // Function call cntBalancedParenthesis(s, N);// This code is contributed by todaysgaurav </script> |
Output:
2
Time Complexity: O(N) where n is number of elements in given string. As, we are using a loop to traverse N times so it will cost us O(N) time
Auxiliary Space: O(1), as we are not using extra space.
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!