#2222

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Number of Ways to Select Buildings

Solve Number of Ways to Select Buildings by counting alternating 3-building patterns with state transitions over the binary string.

string dynamic programming prefix sum

Problem Statement

You are given a binary string s where each character marks a building type on a street. You need to choose exactly three building indices in increasing order for inspection.

A choice is valid only when adjacent selected buildings are different, so the chosen three-character pattern must alternate. In practice, that means only 010 and 101 count. Return how many index triples satisfy that rule.

Examples

Example 1

Input: s = "001101"

Output: 6

The following sets of indices selected are valid:

[0,2,4] from "001101" forms "010"
[0,3,4] from "001101" forms "010"
[1,2,4] from "001101" forms "010"
[1,3,4] from "001101" forms "010"
[2,4,5] from "001101" forms "101"
[3,4,5] from "001101" forms "101" No other selection is valid. Thus, there are 6 total ways.

Example 2

Input: s = "11100"

Output: 0

It can be shown that there are no valid selections.

Constraints

3 <= s.length <= 105
s[i] is either '0' or '1'.

Solution Approach

Start from the only two valid patterns

This problem looks like a generic subsequence count at first, but it is much narrower: the only valid three-building selections are 010 and 101. Once you reduce the target set to those two patterns, the task becomes counting alternating subsequences of length three instead of exploring all triples. That removes the brute-force O(n^3) trap immediately.

Use state transition dynamic programming

Track how many ways you have built short alternating patterns while scanning s from left to right. Maintain counts for single 0s and 1s, then counts for pairs 01 and 10, then extend those pairs into triples 010 and 101. When you read a 0, it can start a new 0, extend previous 1 into 10, and complete previous 01 into 010. When you read a 1, do the symmetric updates for 1, 01, and 101.

See the same idea as prefix-suffix counting

Another clean view is to treat each index as the middle building. If s[i] is 0, then every 1 before i can pair with every 1 after i to form 101. If s[i] is 1, then every 0 before i can pair with every 0 after i to form 010. This matches the DP transitions exactly and explains why the example s = 001101 gives 6: each middle position contributes a product of opposite-type counts on its left and right.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The optimized solution runs in O(n) time because each character updates a constant number of DP states or contributes one prefix-suffix product. Space is O(1) for the state-transition version, or O(n) if you explicitly store prefix arrays, though that extra storage is not required for this problem.

What Interviewers Usually Probe

They hint that only 010 and 101 matter, which is a direct push away from checking all triples.
They ask for a linear solution under length 10^5, so any nested loop over candidate triples is dead on arrival.
They mention Dynamic Programming and Prefix Sum together, which usually means counting subsequences through running state totals rather than recursion.

Common Pitfalls or Variants

Common pitfalls

Counting contiguous substrings instead of subsequences, which misses valid picks with gaps between buildings.
Updating DP states in the wrong order and accidentally reusing the current character twice in one transition.
Using a 32-bit integer even though the number of valid triples can grow large for long strings.

Follow-up variants

Count alternating subsequences of length k instead of exactly three buildings.
Return separate counts for pattern 010 and pattern 101 rather than their total.
Generalize from a binary string to a small alphabet and count subsequences with no equal adjacent selected characters.

FAQ

What is the main trick in Number of Ways to Select Buildings?

The main trick is noticing that every valid selection must form either 010 or 101. That lets you count alternating subsequences directly instead of testing every triple of indices.

Why is state transition dynamic programming a good fit here?

Because each new character can only affect a small set of partial patterns. A 0 can start 0, extend 1 into 10, and finish 01 into 010, while a 1 does the symmetric work for 1, 01, and 101.

Can this problem be solved with prefix sums too?

Yes. For each position, treat it as the middle building and multiply the count of opposite-type buildings on the left by the count of opposite-type buildings on the right. Summing those products over all indices gives the answer.

Why does s = 001101 return 6?

The valid triples are exactly the subsequences forming 010 or 101. In this string, four selections produce 010 and two selections produce 101, giving a total of 6 valid ways.

What is the most common mistake on this problem?

The most common mistake is thinking the three buildings must be adjacent. They only need increasing indices, so this is a subsequence-counting problem, not a substring or sliding-window problem.

terminal

Solution

Solution 1: Counting + Enumeration

According to the problem description, we need to choose $3$ buildings, and two adjacent buildings cannot be of the same type.

1

2

3

4

5

6

7

8

9

10

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 ans

Continue Practicing

#2209 minimum white tiles after covering with carpets #1871 jump game vii #2218 maximum value of k coins from piles