[Leetcode] 696. Count Binary Substrings 解題報告

題目：

Give 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.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.
      

Example 2:

Input: "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1's and 0's.
      

Note:

• s.length

   will be between 1 and 50,000.

• s

   will only consist of "0" or "1" characters.

  思路：

  首先統計出字元串中連續出現的0的個數以及連續出現的1的個數，然後檢視相鄰的0和1最多可以構成多少個符合條件的子串即可。

  代碼：

  class Solution {
  public:
      int countBinarySubstrings(string s) {
          if (s.length() == 0) {
              return 0;
          }
          vector<int> counts;
          counts.push_back(1);
          for (int i = 1; i < s.length(); ++i) {
              if (s[i] == s[i - 1]) {
                  ++counts.back();
              }
              else {
                  counts.push_back(1);
              }
          }
          int ret = 0;
          for (int i = 0; i + 1 < counts.size(); ++i) {
              ret += min(counts[i], counts[i + 1]);
          }
          return ret;
      }
  };