Let's make this one less mysterious. For 696. Count Binary Substrings, the solution in this repository is mainly a binary search solution.
Guide
What?
Before optimizing anything, pin down what information is still useful after each move. Instead of trying to be clever immediately, read the code as a sequence of questions:
- What state are we keeping?
- How do we move from one state to the next?
- When do we know the answer is already determined?
For this file, the main tools are: binary search, two pointers.
Guide
When?
Use this approach when the hard part is not syntax, but deciding what must stay true after every update. The accepted code reduces that pressure by storing exactly the information that remains useful later.
The important function names to track are countBinarySubstrings.
Guide
Why?
The solution works because it narrows the problem until every update has a clear reason to exist.
- The final return is not magic; it is the invariant after the loops or recursion have finished doing their accounting.
Guide
How?
Walk through the solution in this order:
- Initialize the memory or helper structure.
- Process candidates in the order the invariant expects.
- Update the answer only when the current state is valid.
- Return the value that represents the fully processed input.
The most important competitive-programming habit here is to trust the invariant. Once the invariant is right, the loops become much less scary.
Guide
Complexity
- Time: O(n) to O(n log n), depending on the dominant loop or data structure operation
- Space: O(n) in the usual case for auxiliary containers or recursion
Guide
C++ Solution
Your submission
The accepted solution
solution.cpp
01/**
02Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively.
03
04Substrings that occur multiple times are counted the number of times they occur.
05
06Example 1:
07Input: "00110011"
08Output: 6
09Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
10
11Notice that some of these substrings repeat and are counted the number of times they occur.
12
13Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.
14Example 2:
15Input: "10101"
16Output: 4
17Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.
18Note:
19
20s.length will be between 1 and 50,000.
21s will only consist of "0" or "1" characters.
22**/
23
24//Runtime: 1752 ms, faster than 5.41% of C++ online submissions for Count Binary Substrings.
25//Memory Usage: 13.1 MB, less than 94.03% of C++ online submissions for Count Binary Substrings.
26class Solution {
27public:
28 int countBinarySubstrings(string s) {
29 int count = 0;
30
31 for(int i = 0; i < s.size(); i++){
32 int latterHead = i+1;
33 for(;latterHead < s.size();latterHead++){
34 if(s[latterHead]!=s[i]) break;
35 }
36 //the latter part's length won't match the former part's
37 //latterHead-i: former part's length
38 //s.size()-1-(latterHead-1): the remaining length
39 if(s.size()-1-(latterHead-1) < latterHead-i) continue;
40 bool legal = true;
41 int latterTail = latterHead;
42 for(;latterTail<=latterHead-1+latterHead-i;latterTail++){
43 if(s[i]==s[latterTail]){
44 legal = false;
45 break;
46 }
47 }
48 if(legal){
49 //latterHead - i: former part's length
50 //Method 1(TLE)
51 count+=1;
52
53 //Method 2(Accepted)
54 //length x former part implies x legal substrings
55 //record the substring and skip them
56 count+=(latterHead-i);
57 i+=(latterHead-i-1);
58
59 // cout << i << " " << latterTail << endl;
60 }
61 }
62
63 return count;
64 }
65};
66
67//Runtime: 48 ms, faster than 29.90% of C++ online submissions for Count Binary Substrings.
68//Memory Usage: 16.8 MB, less than 16.42% of C++ online submissions for Count Binary Substrings.
69/**
70Approach #1: Group By Character [Accepted]
71Intuition
72
73We can convert the string s into an array groups that represents the length of same-character contiguous blocks within the string. For example, if s = "110001111000000", then groups = [2, 3, 4, 6].
74
75For every binary string of the form '0' * k + '1' * k or '1' * k + '0' * k, the middle of this string must occur between two groups.
76
77Let's try to count the number of valid binary strings between groups[i] and groups[i+1]. If we have groups[i] = 2, groups[i+1] = 3, then it represents either "00111" or "11000". We clearly can make min(groups[i], groups[i+1]) valid binary strings within this string. Because the binary digits to the left or right of this string must change at the boundary, our answer can never be larger.
78
79Algorithm
80
81Let's create groups as defined above. The first element of s belongs in it's own group. From then on, each element either doesn't match the previous element, so that it starts a new group of size 1; or it does match, so that the size of the most recent group increases by 1.
82
83Afterwards, we will take the sum of min(groups[i-1], groups[i]).
84**/
85/**
86Complexity Analysis
87Time Complexity: O(N), where N is the length of s.
88Every loop is through O(N) items with O(1) work inside the for-block.
89Space Complexity: O(N), the space used by groups.
90**/
91/**
92class Solution {
93public:
94 int countBinarySubstrings(string s) {
95 int count = 0;
96 vector<int> groups;
97 groups.push_back(1);
98
99 for(int i = 1; i < s.size(); i++){
100 if(s[i]!=s[i-1]){
101 groups.push_back(1);
102 }else{
103 groups[groups.size()-1]+=1;
104 }
105 }
106
107 for(int i = 1; i < groups.size(); i++){
108 count += min(groups[i], groups[i-1]);
109 }
110
111 return count;
112 }
113};
114**/
115
116//Runtime: 40 ms, faster than 80.93% of C++ online submissions for Count Binary Substrings.
117//Memory Usage: 13.1 MB, less than 94.03% of C++ online submissions for Count Binary Substrings.
118/**
119Approach #2: Linear Scan [Accepted]
120Intuition and Algorithm
121
122We can amend our Approach #1 to calculate the answer on the fly.
123Instead of storing groups, we will remember only prev = groups[-2] and cur = groups[-1].
124Then, the answer is the sum of min(prev, cur) over each different final (prev, cur) we see.
125**/
126/**
127Complexity Analysis
128Time Complexity: O(N), where N is the length of s.
129Every loop is through O(N) items with O(1) work inside the for-block.
130Space Complexity: O(1), the space used by prev, cur, and ans.
131**/
132/**
133class Solution {
134public:
135 int countBinarySubstrings(string s) {
136 int count = 0, prev = 0, cur = 1;
137
138 for(int i = 1; i < s.size(); i++){
139 if(s[i]!=s[i-1]){
140 count += min(prev, cur);
141 prev = cur;
142 cur = 1;
143 }else{
144 cur++;
145 }
146 }
147
148 return count + min(prev, cur);
149 }
150};
151**/Cost
Complexity
Time
O(n) to O(n log n), depending on the dominant loop or data structure operation
Dominated by the main traversal, recursion, or data-structure operations in the code.
Space
O(n) in the usual case for auxiliary containers or recursion
Auxiliary state plus the answer structure where the problem requires one.