Given a binary string S, the task is to find the minimum number of repetitive replacements of substring “01” to string “110” such that there doesn’t exist any substring “01” in the given string S.
Examples:
Input: S = “01”
Output: 1
Explanation:
Below are the operations performed:
Operation 1: Choosing substring (0, 1) in the string “01” and replacing it with “110” modifies the given string to “110”.
After the above operations, the string S(= “110”) doesn’t contain any substring as “01”. Therefore, the total number of operation required is 1.Input: S = “001”
Output:3
Explanation:
Below are the operations performed:
Operation 1: Choosing substring (1, 2) in the string “001” and replacing it with “110” modifies the given string to “0110”.
Operation 2: Choosing substring (0, 1) in the string “0110” and replacing it with “110” modifies the given string to “11010”.
Operation 3: Choosing substring (2, 3) in the string “11010” and replacing it with “110” modifies the given string to “111100”.
After the above operations, the string S(= “111100”) doesn’t contain any substring as “01”. Therefore, the total number of operation required is 3.
Approach: The given problem can be solved using the Greedy Approach. The operation is whenever a substring “01” is found it is replaced with “110” and now the number of ‘1’ is present on the right side of this ‘0’ forms substring “01” which takes part in changing the string to “110”. Therefore, the idea is to traverse the string from the end and whenever ‘0’ occurs, perform the given operation until the number of 1s present on the right side. Follow the steps below to solve the problem:
- Initialize two variables, say ans and cntOne both as 0 to store the minimum number of operations performed and count of consecutive 1s from the end during traversal.
- Traverse the given string S from the end and perform the following steps:
- If the current character is 0, then increment the ans by the number of consecutive 1s obtained till now and twice the value of the count of consecutive 1s.
- Otherwise, increment the value of cntOne by 1.
- After completing the above steps, print the value of ans as the minimum number of 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 the minimum number// of replacement of "01" with "110"// s.t. S doesn't contain substring "10"void minimumOperations(string S, int N){ // Stores the number of operations // performed int ans = 0; // Stores the resultant count // of substrings int cntOne = 0; // Traverse the string S from end for (int i = N - 1; i >= 0; i--) { // If the current character // is 0 if (S[i] == '0') { ans += cntOne; cntOne *= 2; } // If the current character // is 1 else cntOne++; } // Print the result cout << ans;}// Driver Codeint main(){ string S = "001"; int N = S.length(); minimumOperations(S, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to find the minimum number // of replacement of "01" with "110" // s.t. S doesn't contain substring "10" public static void minimumOperations(String S, int N) { // Stores the number of operations // performed int ans = 0; // Stores the resultant count // of substrings int cntOne = 0; // Traverse the string S from end for (int i = N - 1; i >= 0; i--) { // If the current character // is 0 if (S.charAt(i) == '0') { ans += cntOne; cntOne *= 2; } // If the current character // is 1 else cntOne++; } // Print the result System.out.println(ans); } // Driver Code public static void main(String[] args) { String S = "001"; int N = S.length(); minimumOperations(S, N); }} // This code is contributed by Potta Lokesh |
Python3
# Python3 program for the above approach# Function to find the minimum number# of replacement of "01" with "110"# s.t. S doesn't contain substring "10"def minimumOperations(S, N): # Stores the number of operations # performed ans = 0 # Stores the resultant count # of substrings cntOne = 0 # Traverse the string S from end i = N - 1 while(i >= 0): # If the current character # is 0 if (S[i] == '0'): ans += cntOne cntOne *= 2 # If the current character # is 1 else: cntOne += 1 i -= 1 # Print the result print(ans)# Driver Codeif __name__ == '__main__': S = "001" N = len(S) minimumOperations(S, N)# This code is contributed by ipg2016107 |
C#
// C# program for the above approachusing System;class GFG{// Function to find the minimum number// of replacement of "01" with "110"// s.t. S doesn't contain substring "10"public static void minimumOperations(string S, int N){ // Stores the number of operations // performed int ans = 0; // Stores the resultant count // of substrings int cntOne = 0; // Traverse the string S from end for(int i = N - 1; i >= 0; i--) { // If the current character // is 0 if (S[i] == '0') { ans += cntOne; cntOne *= 2; } // If the current character // is 1 else cntOne++; } // Print the result Console.WriteLine(ans);}// Driver codestatic void Main(){ string S = "001"; int N = S.Length; minimumOperations(S, N);}}// This code is contributed by abhinavjain194 |
Javascript
<script> // JavaScript program for the above approach // Function to find the minimum number // of replacement of "01" with "110" // s.t. S doesn't contain substring "10" function minimumOperations(S, N) { // Stores the number of operations // performed let ans = 0; // Stores the resultant count // of substrings let cntOne = 0; // Traverse the string S from end for (let i = N - 1; i >= 0; i--) { // If the current character // is 0 if (S[i] == '0') { ans += cntOne; cntOne *= 2; } // If the current character // is 1 else cntOne++; } // Print the result document.write(ans); } // Driver Code let S = "001"; let N = S.length; minimumOperations(S, N); // This code is contributed by Potta Lokesh </script> |
3
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
