C++ में बाइनरी स्ट्रिंग से सबस्ट्रिंग 010 को हटाने के लिए न्यूनतम कदम

समस्या कथन

एक बाइनरी स्ट्रिंग को देखते हुए, कार्य इस बाइनरी स्ट्रिंग से सबस्ट्रिंग 010 को हटाने के लिए न्यूनतम चरणों की गणना करना है

उदाहरण

यदि इनपुट स्ट्रिंग 010010 है तो 2 चरणों की आवश्यकता है

• पहले 0 को 1 में बदलें। अब स्ट्रिंग 110010 हो जाती है
• अंतिम 0 को 1 में बदलें। अब अंतिम स्ट्रिंग 110011 हो जाती है

एल्गोरिदम

1. Iterate the string from index 0 sto n-2
2. If in binary string has consecutive three characters ‘0’, ‘1’, ‘0’ then any one character can be changed
Increase the loop counter by 2

उदाहरण

#include <bits/stdc++.h>
using namespace std;
int getMinSteps(string str) { 
   int cnt = 0;
   for (int i = 0; i < str.length() - 2; ++i) {
      if (str[i] == '0' && str[i + 1] == '1' && str[i+ 2] == '0') {
         ++cnt;
         i += 2;
      }
   }
   return cnt;
}
int main() {
   string str = "010010";
   cout << "Minimum required steps = " << getMinSteps(str)
   << endl;
   return 0;
}

जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है

आउटपुट

Minimum required steps = 2