Given a binary string str of size N, the task is to minimize the length of given binary string by removing even length substrings consisting of sam characters, i.e. either 0s or 1s only, from the string any number of times. Finally, print the modified string.
Examples:
Input: str =”101001″
Output: “10”
Explanation: The string can be minimized in the following manner: “101001″ -> “1011” -> “10”.Input: str = “00110”
Output: “0”
Explanation: The string can be minimized in the following manner: “00110″ -> “110″ -> “0”.
Approach: The idea is to use a stack to solve the problem. While traversing the string, if the current character is found to be same as the top element of the stack, pop the element from the stack. After traversal, print the stack from bottom to top. Follow the steps below to solve the problem:
- Declare a stack and push the first character of the string str into the stack.
- Traverse the string str over the range of indices [1, N – 1] using the variable i.
- If the stack is empty, then push the character str[i] into the stack.
- Otherwise, check if str[i] is equal to the top of the stack. If found to be true, pop it from the stack. Otherwise, push the character str[i] to it.
- After completing the above steps, print the stack from bottom to top.
Below is the implementation of the above approach.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Recursive function to print stack// elements from bottom to top without// changing their ordervoid PrintStack(stack<char> s){ // If stack is empty if (s.empty()) return; char x = s.top(); // Pop top element of the stack s.pop(); // Recursively call the // function PrintStack PrintStack(s); // Print the stack element // from the bottom cout << x; // Push the same element onto the // stack to preserve the order s.push(x);}// Function to minimize binary string// by removing substrings consisting// of same charactervoid minString(string s){ // Declare a stack of characters stack<char> Stack; // Push the first character of // the string into the stack Stack.push(s[0]); // Traverse the string s for (int i = 1; i < s.size(); i++) { // If Stack is empty if (Stack.empty()) { // Push current character // into the stack Stack.push(s[i]); } else { // Check if the current // character is same as // the top of the stack if (Stack.top() == s[i]) { // If true, pop the // top of the stack Stack.pop(); } // Otherwise, push the // current element else { Stack.push(s[i]); } } } // Print stack from bottom to top PrintStack(Stack);}// Driver Codeint main(){ string str = "101001"; minString(str); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Recursive function to print stack// elements from bottom to top without// changing their orderstatic void PrintStack(Stack<Character> s){ // If stack is empty if (s.isEmpty()) return; char x = s.peek(); // Pop top element of the stack s.pop(); // Recursively call the // function PrintStack PrintStack(s); // Print the stack element // from the bottom System.out.print(x); // Push the same element onto the // stack to preserve the order s.add(x);}// Function to minimize binary String// by removing subStrings consisting// of same characterstatic void minString(String s){ // Declare a stack of characters Stack<Character> Stack = new Stack<Character>(); // Push the first character of // the String into the stack Stack.add(s.charAt(0)); // Traverse the String s for (int i = 1; i < s.length(); i++) { // If Stack is empty if (Stack.isEmpty()) { // Push current character // into the stack Stack.add(s.charAt(i)); } else { // Check if the current // character is same as // the top of the stack if (Stack.peek() == s.charAt(i)) { // If true, pop the // top of the stack Stack.pop(); } // Otherwise, push the // current element else { Stack.push(s.charAt(i)); } } } // Print stack from bottom to top PrintStack(Stack);}// Driver Codepublic static void main(String[] args){ String str = "101001"; minString(str);}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach# Recursive function to print stack# elements from bottom to top without# changing their orderdef PrintStack(s) : # If stack is empty if (len(s) == 0) : return; x = s[-1]; # Pop top element of the stack s.pop(); # Recursively call the # function PrintStack PrintStack(s); # Print the stack element # from the bottom print(x, end=""); # Push the same element onto the # stack to preserve the order s.append(x);# Function to minimize binary string# by removing substrings consisting# of same characterdef minString(s) : # Declare a stack of characters Stack = []; # Push the first character of # the string into the stack Stack.append(s[0]); # Traverse the string s for i in range(1, len(s)) : # If Stack is empty if (len(Stack) == 0) : # Push current character # into the stack Stack.append(s[i]); else: # Check if the current # character is same as # the top of the stack if (Stack[-1] == s[i]) : # If true, pop the # top of the stack Stack.pop(); # Otherwise, push the # current element else : Stack.append(s[i]); # Print stack from bottom to top PrintStack(Stack);# Driver Codeif __name__ == "__main__" : string = "101001"; minString(string); # This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Recursive function to print stack// elements from bottom to top without// changing their orderstatic void PrintStack(Stack<char> s){ // If stack is empty if (s.Count == 0) return; char x = s.Peek(); // Pop top element of the stack s.Pop(); // Recursively call the // function PrintStack PrintStack(s); // Print the stack element // from the bottom Console.Write((char)x); // Push the same element onto the // stack to preserve the order s.Push(x);}// Function to minimize binary String// by removing subStrings consisting// of same characterstatic void minString(String s){ // Declare a stack of characters Stack<char> Stack = new Stack<char>(); // Push the first character of // the String into the stack Stack.Push(s[0]); // Traverse the String s for (int i = 1; i < s.Length; i++) { // If Stack is empty if (Stack.Count == 0) { // Push current character // into the stack Stack.Push(s[i]); } else { // Check if the current // character is same as // the top of the stack if (Stack.Peek() == s[i]) { // If true, pop the // top of the stack Stack.Pop(); } // Otherwise, push the // current element else { Stack.Push(s[i]); } } } // Print stack from bottom to top PrintStack(Stack);}// Driver Codepublic static void Main(String[] args){ String str = "101001"; minString(str);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// js program for the above approach// Recursive function to print stack// elements from bottom to top without// changing their orderfunction PrintStack( s){ // If stack is empty if (s.length == 0) return; let x = s[s.length-1]; // Pop top element of the stack s.pop(); // Recursively call the // function PrintStack PrintStack(s); // Print the stack element // from the bottom document.write(x); // Push the same element onto the // stack to preserve the order s.push(x);}// Function to minimize binary string// by removing substrings consisting// of same characterfunction minString( s){ // Declare a stack of characters let Stack = []; // Push the first character of // the string into the stack Stack.push(s[0]); // Traverse the string s for (let i = 1; i < s.length; i++) { // If Stack is empty if (Stack.length==0) { // Push current character // into the stack Stack.push(s[i]); } else { // Check if the current // character is same as // the top of the stack if (Stack[Stack.length-1] == s[i]) { // If true, pop the // top of the stack Stack.pop(); } // Otherwise, push the // current element else { Stack.push(s[i]); } } } // Print stack from bottom to top PrintStack(Stack);}// Driver Codelet str = "101001"; minString(str);</script> |
Output:
10
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
