Given a string S of size N consisting of only ‘(‘ and ‘)’ only and a positive integer K, the task is to check if the given string can be made a valid parenthesis sequence by moving any characters of the string S to either end of the string at most K number of times.
Examples:
Input: S = “)(“, K = 1
Output: Yes
Explanation: Move S[0] to the end of the string.
Now, the modified string S is “()” which is balanced. Therefore, the number of moves required is 1( = K).Input: S = “()()”, K = 0
Output: Yes
Approach: The given problem can be solved based on the following observations:
- If N is odd or the count of opening and closing brackets are not equal, then it is not possible to make a valid parenthesis sequence.
- The idea is to traverse the given sequence and keep track of the difference of count of opening and closing brackets, and if the difference becomes negative at any index, then move some opening bracket after the current index and move it to the beginning.
Follow the steps below to solve the problem:
- If N is odd or the count of opening and closing brackets are not equal, then it is not possible to make a valid parenthesis sequence. Hence, print “No”. Otherwise, perform the following steps:
- Initialize two variables, say count and ans as 0 that keeps track of the difference of opening and closing brackets and the required number of moves respectively.
- Traverse the given string S and perform the following steps:
- If the current character S[i] is ‘(‘, then increment the value of count by 1.
- Otherwise, decrement the value of count by 1.
- If the count is less than 0, then update the count to 0, and increment the value of ans by 1.
- After completing the above steps, if the value of ans is at most K, then print “Yes”. Otherwise, print “No”.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to check if a valid parenthesis// can be obtained by moving characters// to either end at most K number of timesvoid minimumMoves(string s, int n, int k){ // Base Case 1 if (n & 1) { cout << "No"; return; } // Count of '(' and ')' int countOpen = count(s.begin(), s.end(), '('); int countClose = count(s.begin(), s.end(), ')'); // Base Case 2 if (countOpen != countClose) { cout << "No"; return; } // Store the count of moves required // to make a valid parenthesis int ans = 0; int cnt = 0; // Traverse the string for (int i = 0; i < n; ++i) { // Increment cnt if opening // bracket has occurred if (s[i] == '(') ++cnt; // Otherwise, decrement cnt by 1 else { // Decrement cnt by 1 --cnt; // If cnt is negative if (cnt < 0) { // Update the cnt cnt = 0; // Increment the ans ++ans; } } } // If ans is at most K, then // print Yes. Otherwise print No if (ans <= k) cout << "Yes"; else cout << "No";}// Driver Codeint main(){ string S = ")("; int K = 1; minimumMoves(S, S.length(), K); return 0;} |
Java
// Java program for the above approachimport java.io.*;import java.lang.*;import java.util.*;class GFG{// Function to check if a valid parenthesis// can be obtained by moving characters// to either end at most K number of timesstatic void minimumMoves(String s, int n, int k){ // Base Case 1 if (n % 2 == 1) { System.out.println("No"); return; } // Count of '(' and ')' int countOpen = 0, countClose = 0; for(char ch : s.toCharArray()) if (ch == '(') countOpen++; else if (ch == ')') countClose++; // Base Case 2 if (countOpen != countClose) { System.out.println("No"); return; } // Store the count of moves required // to make a valid parenthesis int ans = 0; int cnt = 0; // Traverse the string for(int i = 0; i < n; ++i) { // Increment cnt if opening // bracket has occurred if (s.charAt(i) == '(') ++cnt; // Otherwise, decrement cnt by 1 else { // Decrement cnt by 1 --cnt; // If cnt is negative if (cnt < 0) { // Update the cnt cnt = 0; // Increment the ans ++ans; } } } // If ans is at most K, then // print Yes. Otherwise print No if (ans <= k) System.out.println("Yes"); else System.out.println("No");}// Driver Codepublic static void main(String[] args){ String S = ")("; int K = 1; minimumMoves(S, S.length(), K);}}// This code is contributed by Kingash |
Python3
# python 3 program for the above approach# Function to check if a valid parenthesis# can be obtained by moving characters# to either end at most K number of timesdef minimumMoves(s, n, k): # Base Case 1 if (n & 1): print("No") return # Count of '(' and ')' countOpen = s.count('(') countClose = s.count(')') # Base Case 2 if (countOpen != countClose): print("No") return # Store the count of moves required # to make a valid parenthesis ans = 0 cnt = 0 # Traverse the string for i in range(n): # Increment cnt if opening # bracket has occurred if (s[i] == '('): cnt += 1 # Otherwise, decrement cnt by 1 else: # Decrement cnt by 1 cnt -= 1 # If cnt is negative if (cnt < 0): # Update the cnt cnt = 0 # Increment the ans ans += 1 # If ans is at most K, then # print Yes. Otherwise print No if (ans <= k): print("Yes") else: print("No")# Driver Codeif __name__ == "__main__": S = ")(" K = 1 minimumMoves(S, len(S), K) # This code is contributed by ukasp. |
C#
// C# program for the above approachusing System;class GFG{// Function to check if a valid parenthesis// can be obtained by moving characters// to either end at most K number of timesstatic void minimumMoves(string s, int n, int k){ // Base Case 1 if (n % 2 == 1) { Console.WriteLine("No"); return; } // Count of '(' and ')' int countOpen = 0, countClose = 0; foreach(char ch in s.ToCharArray()) if (ch == '(') countOpen++; else if (ch == ')') countClose++; // Base Case 2 if (countOpen != countClose) { Console.WriteLine("No"); return; } // Store the count of moves required // to make a valid parenthesis int ans = 0; int cnt = 0; // Traverse the string for(int i = 0; i < n; ++i) { // Increment cnt if opening // bracket has occurred if (s[i] == '(') ++cnt; // Otherwise, decrement cnt by 1 else { // Decrement cnt by 1 --cnt; // If cnt is negative if (cnt < 0) { // Update the cnt cnt = 0; // Increment the ans ++ans; } } } // If ans is at most K, then // print Yes. Otherwise print No if (ans <= k) Console.WriteLine("Yes"); else Console.WriteLine("No");}// Driver Codestatic void Main() { string S = ")("; int K = 1; minimumMoves(S, S.Length, K);}}// This code is contributed by SoumikMondal |
Javascript
<script>// JavaScript program for the above approach// Function to check if a valid parenthesis// can be obtained by moving characters// to either end at most K number of timesfunction minimumMoves(s,n,k){ // Base Case 1 if (n & 1) { document.write("No"); return; } // Count of '(' and ')' var countOpen = 0; var i; for(i=0;i<s.length;i++){ if(s[i]=="(") countOpen++; } var countClose = 0; for(i=0;i<s.length;i++){ if(s[i]==")") countClose++; }; // Base Case 2 if (countOpen != countClose) { document.write("No"); return; } // Store the count of moves required // to make a valid parenthesis var ans = 0; var cnt = 0; // Traverse the string for (i = 0; i < n; ++i) { // Increment cnt if opening // bracket has occurred if (s[i] == '(') ++cnt; // Otherwise, decrement cnt by 1 else { // Decrement cnt by 1 --cnt; // If cnt is negative if (cnt < 0) { // Update the cnt cnt = 0; // Increment the ans ++ans; } } } // If ans is at most K, then // print Yes. Otherwise print No if (ans <= k) document.write("Yes"); else document.write("No");}// Driver Code var S = ")("; var K = 1; minimumMoves(S, S.length, K);</script> |
Output:
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
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!