MediumNo. 2222
Number of Ways to Select Buildings — LeetCode 2222 Python Solution
- Pattern
- Prefix Sum
- Topics
- String, Dynamic Programming, Prefix Sum
- Reading time
- 2 min
- Source
- leetcode.com
The problem
You are given a 0-indexed binary string s which represents the types of buildings along a street where: s[i] = '0' denotes that the ith building is an office and s[i] = '1' denotes that the ith building is a restaurant. As a city official, you would like to select 3 buildings for random inspection.
Example
- Input
- s = "001101"
- Output
- 6
- Explanation
- The following sets of indices selected are valid:
Python solution
class Solution:
def numberOfWays(self, s: str) -> int:
l = [0, 0]
r = [s.count("0"), s.count("1")]
ans = 0
for x in map(int, s):
r[x] -= 1
ans += l[x ^ 1] * r[x ^ 1]
l[x] += 1
return ansComplexity
- Time
- O(n)where n is the length of the string s
- Space · auxiliary
- O(1)
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 2222. Number of Ways to Select Buildings is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0903 | Valid Permutations for DI Sequence | Hard |
| 2209 | Minimum White Tiles After Covering With Carpets | Hard |
| 2478 | Number of Beautiful Partitions | Hard |
| 2218 | Maximum Value of K Coins From Piles | Hard |
| 0010 | Regular Expression Matching | Hard |
| 0022 | Generate Parentheses | Medium |
Frequently asked questions
- How hard is LeetCode 2222. Number of Ways to Select Buildings?
LeetCode 2222. Number of Ways to Select Buildings is rated Medium on LeetCode.
- What is the time complexity of LeetCode 2222. Number of Ways to Select Buildings?
The Python solution on this page runs in O(n), where n is the length of the string s.
- What is the space complexity of LeetCode 2222. Number of Ways to Select Buildings?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 2222. Number of Ways to Select Buildings cover?
LeetCode 2222. Number of Ways to Select Buildings is tagged String, Dynamic Programming and Prefix Sum on LeetCode.