search
HomeBackend DevelopmentC++Minimum number of removals to make a string consist of a string of 0s followed by a string of 1s

Minimum number of removals to make a string consist of a string of 0s followed by a string of 1s

The question "Minimum deletions for string concatenation of 0 substrings" involves working with strings. Given as input a string of 0s and 1s, the result is an integer reflecting the minimum number of 0s that must be eliminated in order to generate a substring of consecutive 0s.

In other words, the problem can be reformulated as: given a string composed of 0s and 1s, how many 0s need to be eliminated in order to make the remaining string contain a continuous period of 0s.

algorithm

Step 1: Variable initialization

  • Define a count variable to record the length of the current zero sequence.

  • Define a max_count variable to track the longest sequence of zeros encountered so far.

  • Set both variables to 0.

Step 2: String traversal

Use a loop to iterate through each character in the string.

Step Three: Zero Detection

If the current character is zero, increment the count variable.

Step 4: One detection

  • If the current character is 1, compare the count variable with the max_count variable.

  • If the count variable is higher than the max_count variable, set the max_count variable equal to the count variable.

  • Reset the count variable to 0.

Step 5: Loop completed

Repeat this process until all characters in the string have been processed.

Step 6: Minimum deletion calculation

The minimum number of deletions required to remove all zeros so that the remaining ones are not separated by any zeros can be calculated by subtracting max_count from the string length.

Step 7: Result Output

Print the results to the console.

Method to follow

  • Dynamic method

  • Iteration method

Method 1: Dynamic method

Dynamic programming can be used to solve this problem efficiently. To create a substring of consecutive 0s, we can create an array dp[], where dp[i] represents the minimum number of 0s that need to be eliminated from the substring s[0...i]. The minimum number of 0s to eliminate from an empty substring is 0, so we can initialize dp[0] to 0.

Then, we can iterate over the string s and update dp[i] to −

  • If s[i] is "0", then dp[i] = dp[i-1], because we can include s[i] in a substring of consecutive 0s or remove them.

  • When s[i] is "1", we must get the index j closest to i, which contains the substring of consecutive 0s. This can be done by iterating from i-1 to 0 and seeing if the substring s[j...i] contains consecutive 0's. If index j is found, then dp[i] = dp[j-1] (i-j 1), where dp[j-1] represents the minimum number of 0's 0...j-1 that must be eliminated from the substring s[ ] and (i-j 1) are the total number of 1's that must be eliminated in order to obtain the substring s[j...i] of consecutive 0's. If no such index j is found, then dp[i] = dp[i-1], since we cannot contain s[i] in a substring of consecutive 0s.

    Finally, in order to obtain a substring of consecutive 0s, the minimum number of 0s that need to be removed from the entire string s is given by dp[n-1], where n is the length of the string s.

Example 1

The following program uses the method we discussed above, first reading the input string from standard input, and then identifying all substrings of 0. Then calculate the length of the longest 0 substring and the length of the string generated by concatenating each 0 substring. To determine the minimum number of eliminations required, it ultimately subtracts the length of the longest 0 substring from the sum of all 0 substrings and displays the result to standard output.

#include <bits/stdc++.h>
using namespace std;

int main() {
   string s = "100100011000110"; // constant input string

   vector<pair<int, int>> substrings; // vector to store start and end indices of each substring of 0s

   int start = -1;
   for (int i = 0; i < s.length(); i++) {
      if (s[i] == '0') {
         if (start == -1) {
         start = i;
         }
      } else {
         if (start != -1) {
         substrings.push_back(make_pair(start, i - 1));
         start = -1;
         }
      }
   }
   if (start != -1) {
      substrings.push_back(make_pair(start, s.length() - 1));
   }

   int totalLength = 0;
   for (auto& p : substrings) {
      totalLength += p.second - p.first + 1;
   }

   int maxLength = 0;
   for (auto& p : substrings) {
      int len = p.second - p.first + 1;
      if (len > maxLength) {
         maxLength = len;
      }
   }

   int removals = totalLength - maxLength;
   cout << "Input string: " << s << endl;
   cout << "Minimum removals: " << removals << endl;

   return 0;
}

Output

Input string: 100100011000110
Minimum removals: 6

Method 2: Iterative method

This method uses a direct iteration method to traverse the given string character by character while updating the values ​​​​of the two variables count and max_count. This method updates the value of the count and max_count variables based on whether the current character is 0 or 1. It then provides the difference between max_count and the length of the longest 0 substring.

The Chinese translation of

Example 2

is:

Example 2

This code is a C software that calculates the minimum number of eliminations required to remove all zeros from a binary string so that the rest are not separated by any zeros. The min_deletions function takes a binary string as input and uses a loop to iterate through each character in the string. The loop increments the count variable every time it encounters zero and resets it to zero when it encounters one. The maximum value of the count variable is saved in max_count, and finally the length of the string is subtracted from max_count to obtain the required minimum number of deletions. The results are then displayed to the user.

#include <iostream> 
#include <string> 
using namespace std; 
 
int min_deletions(string str) { 
   int count = 0, max_count = 0; 
   for (char c : str) { 
      if (c == '0') { 
         count++; 
      } else { 
         max_count = max(max_count, count); 
         count = 0; 
      } 
   } 
    return str.length() - max_count; 
} 
 
int main() { 
   string str = "100010011000110"; 
   int deletions = min_deletions(str); 
   cout << "Minimum deletions needed: " << deletions << endl; 
   return 0; 
} 

Output

Minimum deletion needed: 12 

in conclusion

Determining all the substrings of 0, calculating the length of the string produced by concatenating each substring of 0, and determining the length of the substring with the longest 0 are the three steps in solving the given problem. The length of the largest 0 substring can then be subtracted from the sum of all 0 substrings to obtain the minimum number of deletions required.

The method we use to obtain the answer is simple, efficient, and runs in linear time, making it suitable for large inputs. But it can be further enhanced by applying more sophisticated methods such as dynamic programming.

The above is the detailed content of Minimum number of removals to make a string consist of a string of 0s followed by a string of 1s. For more information, please follow other related articles on the PHP Chinese website!

Statement
This article is reproduced at:tutorialspoint. If there is any infringement, please contact admin@php.cn delete
The Future of C  : Adaptations and InnovationsThe Future of C : Adaptations and InnovationsApr 27, 2025 am 12:25 AM

The future of C will focus on parallel computing, security, modularization and AI/machine learning: 1) Parallel computing will be enhanced through features such as coroutines; 2) Security will be improved through stricter type checking and memory management mechanisms; 3) Modulation will simplify code organization and compilation; 4) AI and machine learning will prompt C to adapt to new needs, such as numerical computing and GPU programming support.

The Longevity of C  : Examining Its Current StatusThe Longevity of C : Examining Its Current StatusApr 26, 2025 am 12:02 AM

C is still important in modern programming because of its efficient, flexible and powerful nature. 1)C supports object-oriented programming, suitable for system programming, game development and embedded systems. 2) Polymorphism is the highlight of C, allowing the call to derived class methods through base class pointers or references to enhance the flexibility and scalability of the code.

C# vs. C   Performance: Benchmarking and ConsiderationsC# vs. C Performance: Benchmarking and ConsiderationsApr 25, 2025 am 12:25 AM

The performance differences between C# and C are mainly reflected in execution speed and resource management: 1) C usually performs better in numerical calculations and string operations because it is closer to hardware and has no additional overhead such as garbage collection; 2) C# is more concise in multi-threaded programming, but its performance is slightly inferior to C; 3) Which language to choose should be determined based on project requirements and team technology stack.

C  : Is It Dying or Simply Evolving?C : Is It Dying or Simply Evolving?Apr 24, 2025 am 12:13 AM

C isnotdying;it'sevolving.1)C remainsrelevantduetoitsversatilityandefficiencyinperformance-criticalapplications.2)Thelanguageiscontinuouslyupdated,withC 20introducingfeatureslikemodulesandcoroutinestoimproveusabilityandperformance.3)Despitechallen

C   in the Modern World: Applications and IndustriesC in the Modern World: Applications and IndustriesApr 23, 2025 am 12:10 AM

C is widely used and important in the modern world. 1) In game development, C is widely used for its high performance and polymorphism, such as UnrealEngine and Unity. 2) In financial trading systems, C's low latency and high throughput make it the first choice, suitable for high-frequency trading and real-time data analysis.

C   XML Libraries: Comparing and Contrasting OptionsC XML Libraries: Comparing and Contrasting OptionsApr 22, 2025 am 12:05 AM

There are four commonly used XML libraries in C: TinyXML-2, PugiXML, Xerces-C, and RapidXML. 1.TinyXML-2 is suitable for environments with limited resources, lightweight but limited functions. 2. PugiXML is fast and supports XPath query, suitable for complex XML structures. 3.Xerces-C is powerful, supports DOM and SAX resolution, and is suitable for complex processing. 4. RapidXML focuses on performance and parses extremely fast, but does not support XPath queries.

C   and XML: Exploring the Relationship and SupportC and XML: Exploring the Relationship and SupportApr 21, 2025 am 12:02 AM

C interacts with XML through third-party libraries (such as TinyXML, Pugixml, Xerces-C). 1) Use the library to parse XML files and convert them into C-processable data structures. 2) When generating XML, convert the C data structure to XML format. 3) In practical applications, XML is often used for configuration files and data exchange to improve development efficiency.

C# vs. C  : Understanding the Key Differences and SimilaritiesC# vs. C : Understanding the Key Differences and SimilaritiesApr 20, 2025 am 12:03 AM

The main differences between C# and C are syntax, performance and application scenarios. 1) The C# syntax is more concise, supports garbage collection, and is suitable for .NET framework development. 2) C has higher performance and requires manual memory management, which is often used in system programming and game development.

See all articles

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Atom editor mac version download

Atom editor mac version download

The most popular open source editor

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

EditPlus Chinese cracked version

EditPlus Chinese cracked version

Small size, syntax highlighting, does not support code prompt function

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!