2147. Number Of Ways To Divide A Long Corridor

Problem Statement in English

You’re given a string corridor where each character is either 'S' (representing a seat) or 'P' (representing a plant).

You need to divide the corridor into sections such that each section contains exactly two seats. The divisions can only be made between plants. Your task is to find the number of ways to divide the corridor into such sections. Since the answer could be large, return it modulo $10^9 + 7$.

Approach

You’ll notice here that the answer is essentially choosing a combination of places to cut the corridor. The only places you can cut are between plants that are between pairs of seats.

So all we really need to do is find the number of plants between each pair of seats, and multiply those counts together to get the total number of ways to divide the corridor.

It does require a little bit of intuition with respect to the combinatorics, but once you see that, the implementation is straightforward.

Solution in Python

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        chairs = corridor.count("S")

        if chairs % 2 or chairs < 2:
            return 0

        spans = []
        MOD = 10**9+7

        l = seats = 0
        for r,v in enumerate(corridor):
            if v == "S":
                seats += 1
            
                if seats == 1:
                    l = r
                elif seats == 2:
                    spans.append((l, r))
                    seats = 0

        res = 1

        for i in range(1, len(spans)):
            res *= ((spans[i][0] - spans[i - 1][1]) % MOD)
            res %= MOD

        return res % MOD

Complexity

• Time: $O(n)$
  Since we traverse the corridor string.

• Space: $O(n)$
  Since we store the spans of seats in a list.

And we are done.