Minimum removal of consecutive similar characters required to empty a Binary String

0 0 6 minutes read

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 empty
int 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 Code
int main()
{
    // Given string S
    string S = "0010100";
 
    // Function Call
    minSteps(S);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to find minimum steps
// to make the String empty
static 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 Code
public 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 approach
from math import ceil
 
# Function to find minimum steps
# to make the empty
def 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 Code
if __name__ == '__main__':
     
    # Given S
    S = "0010100"
 
    # Function Call
    minSteps(S)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to find minimum steps
// to make the string empty
static 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 Code
public 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 empty
function 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

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 code
if __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's
function 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 function
function main() {
    let str = "110001101";
    console.log(minSteps(str));
}
 
// Call the main function
main();

Output

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 zambiatek!