C++ में बाइनरी सबस्ट्रिंग्स की गिनती

मान लीजिए हमारे पास एक स्ट्रिंग s है, हमें उन सन्निहित सबस्ट्रिंग्स की गिनती ढूंढनी है जिनमें 0 और 1 की संख्या समान हो, और इन सबस्ट्रिंग्स में सभी 0 और सभी 1 लगातार समूहित हों। यदि सबस्ट्रिंग्स कई बार आते हैं तो उन्हें उतनी बार गिना जाता है जितनी बार वे होते हैं।

इसलिए, यदि इनपुट "11001100" जैसा है, तो आउटपुट 6 होगा, क्योंकि सबस्ट्रिंग्स हैं "1100", "10", "0011", "01", "1100", "10"।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:

आकार 2 की एक सरणी cnt परिभाषित करें और इसे 0 से भरें
res := 0
i := 0 से s की लंबाई - 1 तक लूप चलाएं:
- num := s[i] - '0' का ASCII
- यदि i == 0 या s[i] != s[i-1], तो:
  - cnt[num] := 0
- cnt[num] को 1 से बढ़ाएं
- यदि cnt[num] <= cnt[1-num], तो:
  - res को 1 से बढ़ाएं
res वापस करें

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

उदाहरण

#include <bits/stdc++.h> 
using namespace std; 
class Solution { 
public: 
    int countBinarySubstrings(string s) { 
        int cnt[2] = { 0 }; 
        int res = 0; 
        for (int i = 0; i < s.length(); ++i) { 
            int num = s[i] - '0'; 
            if (i == 0 || s[i] != s[i - 1]) 
                cnt[num] = 0; 
            ++cnt[num]; 
            if (cnt[num] <= cnt[1 - num]) 
                ++res; 
        } 
        return res; 
    } 
}; 
int main(){ 
    Solution ob; 
    cout << (ob.countBinarySubstrings("11001100")); 
}

इनपुट

"11001100"