We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Number of Ways to Select Buildings

Number: 2325

Difficulty: Medium

Paid? No

Companies: Amazon, Dream11

Problem Description

Given a binary string s representing a row of buildings (where '0' is an office and '1' is a restaurant), we need to select 3 buildings such that no two consecutive selected buildings are of the same type. In other words, the three selected building types must follow either the "010" or "101" pattern. Return the total number of valid ways to select the 3 buildings.

Key Insights

  • The valid patterns of three buildings are "010" and "101".
  • For each potential middle building, count the number of valid left and right buildings that can form a valid triplet.
  • If the middle is '0', use the number of '1's to its left and right for the "101" pattern.
  • If the middle is '1', use the number of '0's to its left and right for the "010" pattern.
  • Use prefix and suffix counts (or running counters) to efficiently get these counts with a single pass over the string.

Space and Time Complexity

Time Complexity: O(n) – We iterate through the string once. Space Complexity: O(1) – Only a few integer counters are used.

Solution

We iterate through the string treating each building as the potential middle building in the triplet. For each index j:

  • If s[j] = '0', then to form a valid "010" pattern, the left building must be '1' and the right building must also be '1'. Multiply the count of '1's seen so far (prefix) by the count of '1's yet to come (suffix).
  • If s[j] = '1', then for a valid "101" pattern, the left must be '0' and the right must also be '0'. Multiply the count of '0's seen so far with the count of '0's remaining. We update prefix counts as we move and decrement the suffix counts accordingly.

Code Solutions

# Python solution with detailed comments

def numberOfWays(s: str) -> int:
    # Initialize suffix counts with total occurrences of '0' and '1'
    suffix0 = s.count('0')
    suffix1 = s.count('1')
    
    # Initialize prefix counters (numbers of '0' and '1' seen so far)
    prefix0, prefix1 = 0, 0
    
    # Counter for valid ways to select 3 buildings
    ways = 0
    
    # Iterate through each building treating it as the middle building
    for char in s:
        if char == '0':
            # Decrease the suffix count for current '0'
            suffix0 -= 1
            # Valid pattern when middle is '0' is "101":
            # left must be '1' (prefix1) and right must be '1' (suffix1)
            ways += prefix1 * suffix1
            # Update the prefix count after processing the current building
            prefix0 += 1
        else:  # char == '1'
            # Decrease the suffix count for current '1'
            suffix1 -= 1
            # Valid pattern when middle is '1' is "010":
            # left must be '0' (prefix0) and right must be '0' (suffix0)
            ways += prefix0 * suffix0
            # Update the prefix count after processing the current building
            prefix1 += 1
    return ways

# Example usage:
print(numberOfWays("001101"))  # Expected output: 6
← Back to All Questions