Removing elements between the two zeros
Given an integer N which shows the size of the string and in the next line given a string which contains a string of character with only zero and one. The task is to remove a single character each time that comes in between the two zero characters.
During each turn, only one character from the string will be removed that satisfies the following condition :
- It must be surrounded by zeroes on both sides.
Examples:
Input : str = β1001
Output : str = β1001βInput : str = β10101
Output : str = β1001β
Use a loop from 1 to N β 1 and check if any element lies between two zeros such that s[i β 1] = β0β and s[i + 1] = β0β. If the condition is satisfied then, delete the character at that position, ad start searching for patterns again.
C++
// C++ program to delete elements between zeros #include <bits/stdc++.h> using namespace std; // Function to find the string // after operation string findstring(string s) { int n = s.length(); // Traversing through string for ( int i = 1; i < n - 1; i++) { // Checking for character // Between two zeros if ((s.at(i - 1) == '0' && s.at(i + 1) == '0' )) { // deleting the character // At specific position s.erase(i, 1); i--; if (i > 0 && s.at(i - 1) == '0' ) i--; // updating the length // of the string n = s.length(); } } return s; } // Drivers code int main() { cout << findstring( "100100" ); return 0; } |
Java
// Java program to delete elements between zeros import java.util.*; public class GFG { // Function to find the string // after operation static String findstring(String s) { int n = s.length(); // use for loop to remove the // character between two zeros for ( int i = 1 ; i < n - 1 ; i++) { // Checking for character // Between two zeros if ((s.charAt(i - 1 ) == '0' && s.charAt(i + 1 ) == '0' )) { // deleting the character // At specific position s = s.substring( 0 , i) + s.substring(i + 1 ); i--; if (i > 0 && s.charAt(i - 1 ) == '0' ) i--; // updating the length // of the string n = s.length(); } } return s; } // Driver code public static void main(String[] args) { String s= "100100" ; System.out.println(findstring(s)); } } |
Python3
# Python3 program to delete elements # between zeros # Function to find the string # after operation def findstring(s): n = len (s) s = list (s) i = 1 # Traversing through string while i < n - 1 : # Checking for character # Between two zeros if (s[i - 1 ] = = '0' and s[i + 1 ] = = '0' ): # Deleting the character # At specific position s.pop(i) i - = 1 if i > 0 and s[i - 1 ] = = '0' : i - = 1 # Updating the length # of the string n = len (s) i + = 1 return ''.join(s) # Driver code if __name__ = = '__main__' : print (findstring( '100100' )) # This code is contributed by rutvik_56 |
C#
// C# program to delete // elements between zeros using System; class GFG { // Function to find the // string after operation static string findstring( string s) { int n = s.Length; string st = "" ; // Traversing through string for ( int i = 1; i < n - 1; i++) { // Checking for character // Between two zeros if ((s[i - 1] == '0' && s[i + 1] == '0' )) { // deleting the character // At specific position st = s.Remove(i, 1); s = st; i--; if (i > 0 && s[i - 1] == '0' ) i--; // updating the length // of the string n = s.Length; } } return s; } // Driver code static void Main() { Console.Write(findstring( "100100" )); } } // This code is contributed by // Manish Shaw(manishshaw1) |
Javascript
<script> // JavaScript program to delete elements // between zeros // Function to find the string // after operation function findstring(s){ let n = s.length s = s.split( '' ) let i = 1 // Traversing through string while (i < n - 1){ // Checking for character // Between two zeros if (s[i - 1] == '0' && s[i + 1] == '0' ){ // Deleting the character // At specific position s.splice(i,1); i -= 1 if (i > 0 && s[i - 1] == '0' ) i -= 1 // Updating the length // of the string n = s.length } i += 1 } return s.join( '' ) } // Driver code document.write(findstring( '100100' ), "</br>" ) // This code is contributed by shinjanpatra </script> |
100
Time Complexity: O(N2), where N is the size of the input string and using erase function to delete the value in the string.
Auxiliary Space: O(1)