Skip to content

2222. Number of Ways to Select Buildings 👍

  • Time: $O(n)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
 public:
  long long numberOfWays(string s) {
    long ans = 0;
    // before[i] := the number of i before the current digit
    vector<int> before(2);
    // after[i] := the number of i after the current digit
    vector<int> after(2);
    after[0] = ranges::count(s, '0');
    after[1] = s.length() - after[0];

    for (const char c : s) {
      const int num = c - '0';
      --after[num];
      if (num == 0)
        ans += before[1] * after[1];
      else
        ans += before[0] * after[0];
      ++before[num];
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
  public long numberOfWays(String s) {
    long ans = 0;
    // before[i] := the number of i before the current digit
    int[] before = new int[2];
    // after[i] := the number of i after the current digit
    int[] after = new int[2];
    after[0] = (int) s.chars().filter(c -> c == '0').count();
    after[1] = s.length() - after[0];

    for (final char c : s.toCharArray()) {
      final int num = c - '0';
      --after[num];
      if (num == 0)
        ans += before[1] * after[1];
      else
        ans += before[0] * after[0];
      ++before[num];
    }

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
  def numberOfWays(self, s: str) -> int:
    ans = 0
    # before[i] := the number of i before the current digit
    before = [0] * 2
    # after[i] := the number of i after the current digit
    after = [0] * 2
    after[0] = s.count('0')
    after[1] = len(s) - after[0]

    for c in s:
      num = int(c)
      after[num] -= 1
      if num == 0:
        ans += before[1] * after[1]
      else:
        ans += before[0] * after[0]
      before[num] += 1

    return ans