Problem Description

You are given a binary string s where each character represents a type of building along a street:

• s[i] = '0' means the building at position i is an office
• s[i] = '1' means the building at position i is a restaurant

Your task is to select exactly 3 buildings for inspection with the constraint that among the 3 selected buildings, no two consecutive buildings (in the order they appear in the original string) can be of the same type.

For example, if s = "001101" and you select buildings at positions 0, 2, and 4 (forming the pattern "010"), this is valid because no two consecutive buildings in your selection have the same type. However, selecting positions 1, 3, and 5 (forming "011") would be invalid because the second and third selected buildings are both restaurants.

The goal is to find the total number of valid ways to select 3 buildings that satisfy this constraint.

Since we need exactly 3 buildings with alternating types, there are only two valid patterns possible:

• "010" - office, restaurant, office
• "101" - restaurant, office, restaurant

The solution counts how many ways we can form these patterns by choosing any 3 positions from the string where the buildings at those positions match one of these alternating patterns.

Intuition

Since we need to select 3 buildings with alternating types, we can think about this problem differently - instead of trying all possible combinations of 3 buildings, we can focus on the middle building of our selection.

The key insight is that once we fix the middle building, the types of the first and third buildings are determined - they must be opposite to the middle one. If the middle building is type x, then both the first and third buildings must be type x ^ 1 (the opposite type).

This leads us to a counting strategy: for each position i in the string that could serve as the middle building:

• Count how many buildings of the opposite type exist to its left
• Count how many buildings of the opposite type exist to its right
• The number of valid selections with building i as the middle is simply the product of these two counts

For example, if building i is a restaurant (1), and there are 3 offices to its left and 2 offices to its right, then there are 3 × 2 = 6 ways to form a valid selection with this building in the middle.

To implement this efficiently, we can maintain two arrays:

• l[0] and l[1] to track the count of offices and restaurants seen so far (to the left)
• r[0] and r[1] to track the count of offices and restaurants remaining (to the right)

As we traverse the string from left to right, for each building we encounter, we update these counts and calculate its contribution to the answer. This allows us to solve the problem in a single pass with O(n) time complexity.

Learn more about Dynamic Programming and Prefix Sum patterns.

Solution Approach

The solution implements the counting strategy we identified in the intuition. Here's how the algorithm works:

Initialization:

• l = [0, 0]: Tracks the count of buildings of each type (0 for offices, 1 for restaurants) to the left of current position
• r = [s.count("0"), s.count("1")]: Initially contains the total count of all offices and restaurants in the entire string (representing everything to the right at the start)
• ans = 0: Accumulator for the final answer

Main Algorithm:

We iterate through each character in the string s, treating each position as a potential middle building:

1. Convert character to integer: x = int(s[i]) gives us 0 for office, 1 for restaurant

2. Update right count: r[x] -= 1

   • Since we're at position i, this building is no longer "to the right", so we decrement its count from r

3. Calculate valid selections: ans += l[x ^ 1] * r[x ^ 1]

   • If current building is type x, we need buildings of type x ^ 1 on both sides
   • x ^ 1 flips the type: if x = 0 (office), then x ^ 1 = 1 (restaurant), and vice versa
   • The number of valid ways with current building as middle = (count of opposite type on left) × (count of opposite type on right)

4. Update left count: l[x] += 1

   • After processing position i, this building becomes part of the "left side" for future positions

Example Walkthrough:

For s = "001101":

• Initial: l = [0, 0], r = [3, 3]
• Position 0 (office): r[0] = 2, calculate 0 * 3 = 0, l[0] = 1
• Position 1 (office): r[0] = 1, calculate 0 * 3 = 0, l[0] = 2
• Position 2 (restaurant): r[1] = 2, calculate 2 * 1 = 2, l[1] = 1
• Position 3 (restaurant): r[1] = 1, calculate 2 * 1 = 2, l[1] = 2
• Position 4 (office): r[0] = 0, calculate 2 * 1 = 2, l[0] = 3
• Position 5 (restaurant): r[1] = 0, calculate 3 * 0 = 0, l[1] = 3
• Total: 0 + 0 + 2 + 2 + 2 + 0 = 6

The time complexity is O(n) as we make a single pass through the string, and space complexity is O(1) as we only use fixed-size arrays.

Example Walkthrough

Let's trace through a small example with s = "00110" to understand how the algorithm counts valid selections.

Setup:

• We need to select 3 buildings with alternating types (either "010" or "101" pattern)
• Strategy: For each position, treat it as the middle building and count valid combinations

Initial State:

• l = [0, 0] (no buildings to the left initially)
• r = [3, 2] (3 offices and 2 restaurants total in the string)
• ans = 0

Step-by-step Processing:

Position 0: '0' (office)

• Current building type: x = 0
• Update right count: r[0] = 3 - 1 = 2 (remove this office from right side)
• Calculate combinations with this as middle:
  • Need restaurants (type 1) on both sides
  • Left restaurants: l[1] = 0
  • Right restaurants: r[1] = 2
  • Contribution: 0 × 2 = 0
• Update left count: l[0] = 0 + 1 = 1
• Running total: ans = 0

Position 1: '0' (office)

• Current building type: x = 0
• Update right count: r[0] = 2 - 1 = 1
• Calculate combinations:
  • Left restaurants: l[1] = 0
  • Right restaurants: r[1] = 2
  • Contribution: 0 × 2 = 0
• Update left count: l[0] = 1 + 1 = 2
• Running total: ans = 0

Position 2: '1' (restaurant)

• Current building type: x = 1
• Update right count: r[1] = 2 - 1 = 1
• Calculate combinations:
  • Need offices (type 0) on both sides
  • Left offices: l[0] = 2
  • Right offices: r[0] = 1
  • Contribution: 2 × 1 = 2
  • This counts: (position 0, position 2, position 4) and (position 1, position 2, position 4)
• Update left count: l[1] = 0 + 1 = 1
• Running total: ans = 2

Position 3: '1' (restaurant)

• Current building type: x = 1
• Update right count: r[1] = 1 - 1 = 0
• Calculate combinations:
  • Left offices: l[0] = 2
  • Right offices: r[0] = 1
  • Contribution: 2 × 1 = 2
  • This counts: (position 0, position 3, position 4) and (position 1, position 3, position 4)
• Update left count: l[1] = 1 + 1 = 2
• Running total: ans = 4

Position 4: '0' (office)

• Current building type: x = 0
• Update right count: r[0] = 1 - 1 = 0
• Calculate combinations:
  • Left restaurants: l[1] = 2
  • Right restaurants: r[1] = 0
  • Contribution: 2 × 0 = 0
• Update left count: l[0] = 2 + 1 = 3
• Running total: ans = 4

Final Answer: 4

The 4 valid selections are:

1. Positions (0, 2, 4): "010" pattern
2. Positions (1, 2, 4): "010" pattern
3. Positions (0, 3, 4): "010" pattern
4. Positions (1, 3, 4): "010" pattern

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the string s. This is because:

• The count() operations each scan through the entire string once, contributing O(n) time
• The main loop iterates through each character in the string exactly once, performing constant-time operations (O(1)) for each character: decrementing r[x], calculating the XOR operations, updating ans, and incrementing l[x]
• Overall: O(n) + O(n) + O(n) = O(n)

The space complexity is O(1). The algorithm uses:

• Two fixed-size arrays l and r, each with 2 elements
• A constant number of variables (ans, x)
• The space usage does not depend on the input size, remaining constant regardless of the length of string s

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding the Problem - Selecting Non-Adjacent Buildings

A common misinterpretation is thinking that the selected buildings must be physically adjacent in the original string. This leads to incorrect solutions that only check consecutive triplets.

Incorrect Approach:

def numberOfWays(self, s: str) -> int:
    count = 0
    # Wrong: Only checking consecutive buildings
    for i in range(len(s) - 2):
        substring = s[i:i+3]
        if substring == "010" or substring == "101":
            count += 1
    return count

Why it's wrong: For s = "00110", this would return 1 (finding "011" doesn't match, "110" doesn't match), but the correct answer is 4 because we can select non-adjacent buildings like positions [0,2,4] forming "010".

Correct Understanding: We select any 3 buildings from anywhere in the string, maintaining their relative order but not requiring adjacency.

2. Overcounting by Not Maintaining Order

Another pitfall is counting combinations instead of subsequences, ignoring the order constraint.

Incorrect Approach:

def numberOfWays(self, s: str) -> int:
    zeros = s.count('0')
    ones = s.count('1')
    # Wrong: This counts unordered combinations
    return zeros * ones * zeros + ones * zeros * ones

Why it's wrong: This counts the same selection multiple times in different orders. For positions [1,3,5], it might count both as firstsecondthird and as thirdfirstsecond.

Solution: The correct approach maintains order by considering each position as a middle element and counting valid left-right pairs.

3. Off-by-One Errors in Count Management

A subtle but critical error occurs when the right count isn't updated before calculating valid ways.

Incorrect Approach:

def numberOfWays(self, s: str) -> int:
    left = [0, 0]
    right = [s.count("0"), s.count("1")]
    ans = 0
  
    for digit in map(int, s):
        opposite = digit ^ 1
        # Wrong: Calculating before updating right count
        ans += left[opposite] * right[opposite]
        right[digit] -= 1  # Should be done BEFORE calculation
        left[digit] += 1
  
    return ans

Why it's wrong: When we're at position i, that building shouldn't be counted as "to the right". Including it in the right count leads to overcounting because we're essentially counting the current building as both the middle element and a right element.

Solution: Always update the right count first to exclude the current position before calculating valid selections.