[LeetCode] 696. Count Binary Substrings

轉自LeetCode

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.

<Solution>

想法如下

• 這題最困難的點，是怎麼計算組合。以 00111 為例，0 有兩個，1 有三個，而會有多少符合條件的 substring 呢？答案是 min(2, 3)，只要能找到這個特性，就可以開始解題

• 計算目前的值有幾個，當值變化了，就做一次總結，利用上述的公式來累加出答案

code 如下

Java