LeetCode/CountBinarySubstrings.cpp at master · royalpranjal/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
public:
    int countBinarySubstrings(string s) {
        // int i = 0, n = s.size(), ans = 0;

        // O(n^2) algorithm
        // while(i < n){
//             bool one = false;
//             int count = 1;

//             if(s[i] == '1'){
//                 one = true;
//             }

//             int j = i-1;

//             while(j >= 0){
//                 if(one){
//                     if(s[j] != '1'){
//                         break;
//                     }
//                     count++;
//                 }
//                 else{
//                     if(s[j] != '0'){
//                         break;
//                     }
//                     count++;
//                 }
//                 j--;
//             }

//             while(j >= 0){
//                 if(one){
//                     if(s[j] == '1'){
//                         break;
//                     }
//                     count--;
//                 }
//                 else{
//                     if(s[j] == '0'){
//                         break;
//                     }
//                     count--;
//                 }
//                 j--;
//             }

//             if(count <= 0){
//                 ans++;
//             }

//             i++;
//         }

        // O(n) algorithm

        int i = 0, n = s.size(), ans = 0;

        while(i < n){
            char curr = s[i];
            int j = i;

            while(j < n && s[j] == curr){
                j++;
            }

            int k = j;
            j--;

            while(k < n && s[k] != curr){
                k++;
            }

            ans += min(j-i+1, k-j-1);

            i = j+1;
        }

        return ans;
    }
};