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 Divide a Long Corridor

Number: 2251

Difficulty: Hard

Paid? No

Companies: Zomato

Problem Description

Given a corridor represented as a 0-indexed string of length n consisting of the characters 'S' (seat) and 'P' (plant), you need to install room dividers to partition the corridor into sections such that each section has exactly two seats (with any number of plants allowed in between). There are already dividers at the left of index 0 and the right of index n - 1 and you can add at most one divider between two consecutive indices (i.e., between i-1 and i for 1 <= i <= n-1). Return the number of different ways to add these dividers such that every section has exactly two seats. Two ways differ if there is at least one position where a divider is placed in one method but not in the other. Since the result can be very large, return it modulo 10^9 + 7. If it is impossible to partition the corridor as required, return 0.

Key Insights

  • The total number of seats must be even; otherwise, it is impossible to create sections with exactly two seats.
  • Record the indices of all seats. The valid partitioning occurs after every pair of seats.
  • The number of ways to insert the divider between two paired groups depends on the number of plants (or the gap) between the second seat of one section and the first seat of the next section.
  • Multiply the possibilities for each gap; take care of modulo arithmetic.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the corridor. We traverse the string once to record seat positions. Space Complexity: O(n), needed for storing the seat indices in the worst-case scenario (e.g. when all characters are seats).

Solution

The approach is as follows:

  1. Traverse the corridor string and record the indices of the seats.
  2. If the total number of seats is not even, return 0.
  3. For each pair boundary (i.e., between the second seat of one section and the first seat of the next section), calculate the number of positions available for placing a divider. This is determined by the difference between the positions of the two seats in the seat index list.
  4. Multiply these options (taking modulo 10^9+7) to get the total number of ways.

This method leverages creating an array of seat indices and then computing the effective gap sizes between critical seats. A simple multiplication across each gap, while handling modulo arithmetic, yields the desired answer.

Code Solutions

# Python solution with line-by-line comments

MOD = 10**9 + 7

def numberOfWays(corridor: str) -> int:
    # Step 1: Collect the indices of all seats in the corridor
    seat_indices = [i for i, ch in enumerate(corridor) if ch == 'S']
    
    # Step 2: Check if seat count is even and at least 2 (necessary for one section)
    if len(seat_indices) % 2 != 0 or len(seat_indices) < 2:
        return 0

    ways = 1
    # Step 3: For every pair boundary between sections
    # Every section must consist of exactly 2 seats. So the dividing boundaries are:
    # between seat_indices[1] and seat_indices[2], seat_indices[3] and seat_indices[4], etc.
    for i in range(1, len(seat_indices) // 2):
        # The gap is calculated as the difference between the first seat of the next section 
        # and the second seat of the previous section.
        gap = seat_indices[2*i] - seat_indices[2*i - 1]
        # Multiply the number of ways by the gap (this represents the available spaces for a divider).
        ways = (ways * gap) % MOD

    return ways

# Example calls to test the function
if __name__ == "__main__":
    print(numberOfWays("SSPPSPS"))  # Expected output: 3
    print(numberOfWays("PPSPSP"))   # Expected output: 1
    print(numberOfWays("S"))        # Expected output: 0
← Back to All Questions