# 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 long ans = 0; // before[i] := # of i before current char vector before(2); // after[i] := # of i after current char vector after(2); after[0] = count(begin(s), end(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] := # of i before current char int[] before = new int[2]; // after[i] := # of i after current char 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] := # of i before current char before = [0] * 2 # after[i] := # of i after current char after = [0] * 2 after[0] = s.count('0') after[1] = len(s) - after[0] for c in s: num = ord(c) - ord('0') after[num] -= 1 if num == 0: ans += before[1] * after[1] else: ans += before[0] * after[0] before[num] += 1 return ans