2222. Number of Ways to Select Buildings

https://leetcode.com/problems/number-of-ways-to-select-buildings/solutions/1907179/java-python-3-one-pass-s-o-1-t-o-n-codes-and-follow-up-w-brief-explanation-and-analysis/

T: O(n)

S: O(1)

```java
class Solution {
    public long numberOfWays(String s) {
        long one = 0;
        long zero = 0;
        long oneZero = 0;
        long zeroOne = 0;
        long result = 0;

        for (char c : s.toCharArray()) {
            if (c == '0') {
                zero++;
                oneZero += one; // 1 0
                result += zeroOne; // 01 0
            } else { // 1
                one++;
                zeroOne += zero; // 0 1
                result += oneZero; // 10 1
            }
        }
        return result;
    }
}
/**

11100

-> 6 different 10


01 0
10 1
   cur


10 -> pre 1 -> cur 0
01 -> pre 0 -> cur 1 

001101


Traverse the input `s`:
1. If encontering `0`, count subsequences ending at current `0`:  `0`, `10` and `010`, `1010`'s, ...,; 
The number of `10` depends on how many `1`s before current `0`, 
the number of `010` depends on how many `01` before current `0`, and the number of `1010` depends on how many `101` before current `0`...;

Similarly,

2. If encontering `1`, count subsequences ending at current `1`:  `1`, `01`, `101`, and `0101`'s; 
The number of `01` depends on how many `0`s before current `1`, 
the number of `101` depends on how many `10` before current `1`, 
and the number of `0101` depends on how many `010` before current `1`...
3. We can observe the above patterns and use a 2-D array `ways` to record the corresponding subsequences, e.g., 
 
	 ways[0][0] - number of `0`'s;
	 ways[1][0] - number of `10`'s;
	 ways[2][0] - number of `010`'s;
	 ways[3][0] - number of `1010`'s;
	 ...
	 ways[0][1] - number of `1`'s;
	 ways[1][1] - number of `01`'s;
	 ways[2][1] - number of `101`'s;
	 ways[3][1] - number of `0101`'s;


```java
    public long numberOfWays(String s, int k) {
     // int k = 3;
        long[][] ways = new long[k][2]; 
        for (int i = 0; i < s.length(); ++i) {
            int idx = s.charAt(i) - '0';
            ++ways[0][idx];
            for (int j = 1; j < k; ++j) {
                ways[j][idx] += ways[j - 1][1 - idx];
            }
        }
        return ways[k - 1][0] + ways[k - 1][1];
    }
```

 */
```