Given a binary string S of length N, the task is to find the minimum number of removal of adjacent similar characters required to empty the given binary string.
Examples:
Input: S = “1100011“
Output: 2
Explanation:
Operation 1: Removal of all 0s modifies S to “1111“.
Operation 2: Removal of all remaining 1s makes S empty.
Therefore, the minimum number of operations required is 2.Input: S = “0010100“
Output: 3
Explanation:
Operation 1: Removal of all 1s modifies S to “000100“.
Operation 2: Removal of all 1s modifies S = “00000“.
Operation 3: Removal of all remaining 0s makes S empty.
Therefore, the minimum number of operations required is 3.
Approach: The given problem can be solved using Greedy Approach. The idea is to delete the consecutive occurrences of the character with a higher frequency. Follow the steps below to solve the problem:
- Traverse the given string S and generate a new string, say newString, by removing consecutive occurrences of the character with higher frequency.
- Finally, print (sizeof(newString) + 1)/2 as the required answer
Explanation: The given string eg : “1100011“ changes 101 as we are skipping the multiple occurrence. After this we are returning (sizeof(newString) + 1)/2 the size of are new string being 3 , 101 -> we first delete the 0 which takes us 1 operation then the new string is 11 next we do just 1 more operation to delete the string 11 , taking a total of 2 operations.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find minimum steps// to make the string emptyint minSteps(string S){ // Stores the modified string string new_str; // Size of string int N = S.length(); int i = 0; while (i < N) { new_str += S[i]; // Removing substring of same // character from modified string int j = i; while (i < N && S[i] == S[j]) ++i; } // Print the minimum steps required cout << ceil((new_str.size() + 1) / 2.0);}// Driver Codeint main(){ // Given string S string S = "0010100"; // Function Call minSteps(S); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function to find minimum steps// to make the String emptystatic void minSteps(String S){ // Stores the modified String String new_str = ""; // Size of String int N = S.length(); int i = 0; while (i < N) { new_str += S.charAt(i); // Removing subString of same // character from modified String int j = i; while (i < N && S.charAt(i) == S.charAt(j)) ++i; } // Print the minimum steps required System.out.print((int)Math.ceil( (new_str.length() + 1) / 2.0));}// Driver Codepublic static void main(String[] args){ // Given String S String S = "0010100"; // Function Call minSteps(S);}}// This code is contributed by Princi Singh |
Python3
# Python3 program for the above approachfrom math import ceil# Function to find minimum steps# to make the emptydef minSteps(S): # Stores the modified string new_str = "" # Size of string N = len(S) i = 0 while (i < N): new_str += S[i] # Removing substring of same character # from modified string j = i while (i < N and S[i] == S[j]): i += 1 # Print the minimum steps required print(ceil((len(new_str) + 1) / 2))# Driver Codeif __name__ == '__main__': # Given S S = "0010100" # Function Call minSteps(S)# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;class GFG{// Function to find minimum steps// to make the string emptystatic void minSteps(string S){ // Stores the modified string string new_str = ""; // Size of string int N = S.Length; int i = 0; while (i < N) { new_str += S[i]; // Removing substring of same // character from modified string int j = i; while (i < N && S[i] == S[j]) ++i; } // Print the minimum steps required Console.Write((int)Math.Ceiling( (new_str.Length + 1) / 2.0));}// Driver Codepublic static void Main(){ // Given string S string S = "0010100"; // Function Call minSteps(S);}}// This code is contributed by SURENDRA_GANGWAR |
Javascript
<script>// Javascript program to implement// the above approach// Function to find minimum steps// to make the string emptyfunction minSteps(S){ // Stores the modified string let new_str = ""; // Size of string let N = S.length; let i = 0; while (i < N) { new_str += S[i]; // Removing substring of same // character from modified string let j = i; while (i < N && S[i] == S[j]) ++i; } // Print the minimum steps required document.write(Math.ceil( (new_str.length + 1) / 2.0));} // Driver Code // Given string S let S = "0010100"; // Function Call minSteps(S) </script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Another Approach:
Count the no. of contiguous subgroups of 1 and 0 and return the minimun no. of subgroups after adding 1 to it.
Steps that were to follow the above approach:
- Initialize two variables sub_of_1 and sub_of_0 with 0 to count the no. of contiguous subgroups of 1 and 0.
- Use a loop and start traversing the string from start to end.
- Check if str[i] = ‘1’ or str[i] = ‘0’, where i = 0,1,2,3….. length of the str-1.
- If str[i] = ‘1’, traverse the contiguous subgroup of 1 till str[i] != ‘0’ by incrementing i. After that increment variable sub_of_1 by 1 and decrement i, as you have reached one index ahead of the index where the subgroup of a is ending.
- If str[i] = ‘0’, traverse the contiguous subgroup of 0 till str[i] != ‘1’ by incrementing i. After that increment variable sub_of_0 by 1 and decrement i, as you have reached one index ahead of the index where the subgroup of 0 is ending.
- Last return the minimum number of subgroups ( min(sub_of_1,sub_of_0) ) after adding 1 to it.
Below is the code to implement the above steps:
C++
#include <bits/stdc++.h>using namespace std;int minSteps(string str) { int sub_of_1 = 0, sub_of_0 = 0; for(int i = 0; i<str.length(); i++){ if(str[i] == '1'){ while(str[i] == '1'){ i++; } sub_of_1++; i--; }else{ while(str[i] == '0'){ i++; } sub_of_0++; i--; } } return min(sub_of_1,sub_of_0)+1;}int main() { string str = "110001101"; cout<<minSteps(str)<<endl; return 0;} |
Java
public class MinSteps { public static int minSteps(String str) { int sub_of_1 = 0, sub_of_0 = 0; for (int i = 0; i < str.length(); i++) { if (str.charAt(i) == '1') { while (i < str.length() && str.charAt(i) == '1') { i++; } sub_of_1++; i--; // Decrement to account for the next character in the loop. } else { while (i < str.length() && str.charAt(i) == '0') { i++; } sub_of_0++; i--; // Decrement to account for the next character in the loop. } } return Math.min(sub_of_1, sub_of_0) + 1; } public static void main(String[] args) { String str = "110001101"; System.out.println(minSteps(str)); }} |
Python3
def minSteps(s): sub_of_1 = 0 sub_of_0 = 0 i = 0 while i < len(s): if s[i] == '1': # Count the consecutive '1's while i < len(s) and s[i] == '1': i += 1 sub_of_1 += 1 i -= 1 # Move back to the last '1' else: # Count the consecutive '0's while i < len(s) and s[i] == '0': i += 1 sub_of_0 += 1 i -= 1 # Move back to the last '0' i += 1 # Return the minimum number of steps needed return min(sub_of_1, sub_of_0) + 1# Driver codeif __name__ == "__main__": str = "110001101" print(minSteps(str)) |
C#
using System;class GFG{ static int Geek(string str) { int subOf1 = 0, subOf0 = 0; for (int i = 0; i < str.Length; i++) { if (str[i] == '1') { while (i < str.Length && str[i] == '1') { i++; } subOf1++; i--; } else { while (i < str.Length && str[i] == '0') { i++; } subOf0++; i--; } } return Math.Min(subOf1, subOf0) + 1; } static void Main(string[] args) { string str = "110001101"; Console.WriteLine(Geek(str)); }} |
Javascript
// Function to find the minimum steps to group substrings of '1's or '0'sfunction minSteps(str) { let subOf1 = 0; let subOf0 = 0; for (let i = 0; i < str.length; i++) { if (str[i] === '1') { // Count consecutive '1's while (i < str.length && str[i] === '1') { i++; } subOf1++; i--; // Decrement to account for the next character in the loop. } else { // Count consecutive '0's while (i < str.length && str[i] === '0') { i++; } subOf0++; i--; // Decrement to account for the next character in the loop. } } // Return the minimum of the two counts plus 1 return Math.min(subOf1, subOf0) + 1;}// Main functionfunction main() { let str = "110001101"; console.log(minSteps(str));}// Call the main functionmain(); |
Output
3
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!
