LeetCode 2222 - Number of Ways to Select Buildings

The problem asks us to count the number of ways to select exactly 3 buildings from a street represented as a binary string s, such that no two consecutive buildings among the selected ones have the same type. Here, 0 represents an office, and 1 represents a restaurant.

leetcodemediumstringdynamic-programmingprefix-sum

LeetCode Problem 2222

Difficulty: 🟡 Medium
Topics: String, Dynamic Programming, Prefix Sum

Solution

Problem Understanding

The problem asks us to count the number of ways to select exactly 3 buildings from a street represented as a binary string s, such that no two consecutive buildings among the selected ones have the same type. Here, 0 represents an office, and 1 represents a restaurant. Essentially, for the three selected buildings at positions i < j < k, the substring s[i]s[j]s[k] must be either "010" or "101".

The input s can be up to length 10^5, so any approach that examines all possible triplets individually (which would be O(n^3)) is infeasible. The expected output is the total number of valid triplets that satisfy the alternating type constraint.

Edge cases to consider include strings with all identical characters (no valid selections), strings of length exactly 3, and strings where valid sequences appear at the boundaries.

Approaches

The brute-force approach would iterate over all possible triplets (i, j, k) and check whether s[i] != s[j] != s[k] in the correct alternating pattern. This is correct but highly inefficient with a complexity of O(n^3), which is unacceptable for n = 10^5.

The key observation for an optimal solution is that a valid 3-building sequence must follow "010" or "101". We can precompute prefix sums of the counts of '0' and '1' up to each position. Then, for each position j chosen as the middle building, we can count valid left and right buildings based on the type of s[j]. Specifically, if s[j] == '0', the number of valid triplets with s[j] in the middle is (number of '1's to the left) * (number of '1's to the right). Similarly, if s[j] == '1', it is (number of '0's to the left) * (number of '0's to the right). Summing this over all positions gives the total number of valid triplets in O(n) time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^3) O(1) Enumerates all triplets explicitly
Optimal O(n) O(n) Uses prefix sums to count valid triplets efficiently

Algorithm Walkthrough

  1. Initialize two arrays, prefix0 and prefix1, of length n+1. prefix0[i] stores the number of '0's in s[0..i-1] and prefix1[i] stores the number of '1's in s[0..i-1].
  2. Fill in prefix0 and prefix1 by iterating over the string s. For each position i, increment the respective prefix sum.
  3. Initialize a variable total_ways to 0. This will accumulate the number of valid 3-building selections.
  4. Iterate through each position j in the string, treating it as the middle building.
  5. If s[j] == '0', calculate ways = prefix1[j] * (prefix1[n] - prefix1[j+1]). This represents the number of valid triplets "101" with s[j] in the middle.
  6. If s[j] == '1', calculate ways = prefix0[j] * (prefix0[n] - prefix0[j+1]). This represents the number of valid triplets "010" with s[j] in the middle.
  7. Add ways to total_ways.
  8. After processing all positions, return total_ways.

Why it works: By treating each position as the middle of the triplet, and using precomputed counts of characters on each side, we ensure that all valid sequences are counted exactly once. Prefix sums allow us to efficiently compute left and right counts in O(1) per position, leading to an overall O(n) algorithm.

Python Solution

class Solution:
    def numberOfWays(self, s: str) -> int:
        n = len(s)
        prefix0 = [0] * (n + 1)
        prefix1 = [0] * (n + 1)
        
        for i in range(n):
            prefix0[i+1] = prefix0[i] + (1 if s[i] == '0' else 0)
            prefix1[i+1] = prefix1[i] + (1 if s[i] == '1' else 0)
        
        total_ways = 0
        for j in range(n):
            if s[j] == '0':
                ways = prefix1[j] * (prefix1[n] - prefix1[j+1])
            else:
                ways = prefix0[j] * (prefix0[n] - prefix0[j+1])
            total_ways += ways
        
        return total_ways

The implementation first builds prefix sums for both '0' and '1' characters. Then, for each potential middle building, it calculates the number of valid triplets efficiently using the prefix sums. The multiplication gives all combinations of left and right characters matching the required pattern.

Go Solution

func numberOfWays(s string) int64 {
    n := len(s)
    prefix0 := make([]int, n+1)
    prefix1 := make([]int, n+1)

    for i := 0; i < n; i++ {
        prefix0[i+1] = prefix0[i]
        prefix1[i+1] = prefix1[i]
        if s[i] == '0' {
            prefix0[i+1]++
        } else {
            prefix1[i+1]++
        }
    }

    var totalWays int64 = 0
    for j := 0; j < n; j++ {
        var ways int
        if s[j] == '0' {
            ways = prefix1[j] * (prefix1[n] - prefix1[j+1])
        } else {
            ways = prefix0[j] * (prefix0[n] - prefix0[j+1])
        }
        totalWays += int64(ways)
    }

    return totalWays
}

The Go implementation mirrors the Python version. The main differences include explicit integer conversions for the result to int64 and use of make to initialize slices.

Worked Examples

Example 1: s = "001101"

j (middle) s[j] prefix0[j] prefix1[j] left*right ways Accumulated total
0 '0' 0 0 0*3 = 0 0
1 '0' 1 0 0*3 = 0 0
2 '1' 2 0 2*1 = 2 2
3 '1' 2 1 2*1 = 2 4
4 '0' 2 2 2*1 = 2 6
5 '1' 3 2 3*0 = 0 6

Final answer: 6

Example 2: s = "11100"

All potential middle '1' or '0' characters lead to zero valid combinations because either left or right counts of the required opposite type are zero. Total ways = 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass to compute prefix sums + single pass to compute total ways
Space O(n) Storing prefix sums for '0' and '1'

The algorithm scales linearly with the string length and efficiently handles the upper bound of 10^5 characters.

Test Cases

# Provided examples
assert Solution().numberOfWays("001101") == 6  # Mixed pattern
assert Solution().numberOfWays("11100") == 0   # No valid triplets

# Boundary cases
assert Solution().numberOfWays("010") == 1     # Minimal valid length
assert Solution().numberOfWays("000") == 0     # All same type
assert Solution().numberOfWays("111") == 0     # All same type
assert Solution().numberOfWays("01") == 0      # Too short

# Larger patterns
assert Solution().numberOfWays("010101") == 10  # Multiple alternating triplets
assert Solution().numberOfWays("101010") == 10  # Reverse alternating pattern
assert Solution().numberOfWays("000111") == 0   # No alternating triplets
Test Why
"001101" Standard mixed pattern with multiple valid triplets
"11100" No valid selections due to consecutive same types
"010" Minimal valid triplet length
"000"/"111" All identical, cannot select triplet
"01" Too short to select 3 buildings
"010101"/"101010" Multiple alternating patterns, stress test for correct counting
"000111" Consecutive blocks, should yield zero