LeetCode - 696. Count Binary Substrings

Easy

696. Count Binary Substrings

題目

Given a binary string s, return the number of non-empty 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: s = "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: s = "10101"
Output: 4
Explanation: There are 4 substrings: "10", "01", "10", "01" that have equal number of consecutive 1‘s and 0‘s.

解題思路

這題是計算連續分組的字串題
重點是觀察每一段連續相同字元的長度

例如：

00110011

可以分成：

• 00，長度是 2
• 11，長度是 2
• 00，長度是 2
• 11，長度是 2

每次只需要看相鄰兩段能組出多少合法 substring

• prev：前一段連續相同字元的長度

• cur：目前這一段連續相同字元的長度

• 如果 s[i] == s[i - 1]

  • 代表還在同一段
  • 例如 00 或 111
  • 所以：
    cur++

• 如果 s[i] != s[i - 1]

  • 代表字元改變，目前這一段結束了
  • 可以拿「前一段」和「目前段」配對
  • 可以形成的合法 substring 數量為：
    min(prev, cur)

• 為什麼是 min(prev, cur)？

  • 因為合法 substring 需要有一樣多的 0 和 1
  • 如果前一段長度是 prev
  • 目前段長度是 cur
  • 可以配出的數量就取決於比較短的那一段

例如：

00011

• 前一段 000 長度是 3

• 後一段 11 長度是 2

• 可以形成：

  • 01
  • 0011

• 所以答案是 min(3, 2) = 2

• 字元改變後：

  • prev = cur
  • 目前段變成下一輪的前一段
  • cur = 1
  • 新的一段從目前字元開始

• 最後一段不會再遇到字元改變

  • 所以迴圈結束後要手動結算一次：
    ans += min(prev, cur)

Solution Code

Time Complexity
O(n)

Space Complexity
O(1)

class Solution {
public:
    int countBinarySubstrings(string s) {
        int prev = 0; // 前一段連續相同字元的長度
        int cur = 1;  // 目前這一段連續相同字元的長度
        int ans = 0;

        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == s[i - 1]) { // 還在同一段，例如 00 或 111
                cur++;
            } else {
                // 字元改變，代表目前這一段結束了
                // 可以拿「前一段」和「目前段」配對
                ans += min(prev, cur);

                // 目前段變成下一輪的前一段
                prev = cur;

                // 新的一段從 s[i] 開始，長度是 1
                cur = 1;
            }
        }

        // 最後一段不會再遇到字元改變，所以要手動結算一次
        ans += min(prev, cur);

        return ans;
    }
};