Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Every section needs exactly two seats, fixing the pairing of seats from left to right. Between consecutive seat pairs, a run of p plants offers p + 1 divider positions. These gaps are independent, so their choice counts multiply.

Approach

Count seats first and return zero if the count is zero or odd. Otherwise scan through pairs of seats and count the plants after each pair. If another seat pair follows, multiply the answer by one more than that plant count, modulo 10^9 + 7; a zero-plant gap contributes one. Ignore plants before the first pair and after the last, since adding dividers there would create a section with no seats. Return the product.

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        MOD = 10**9 + 7
        n = len(corridor)
        s = 0

        for x in corridor:
            if x == 'S':
                s += 1

        if not s or s % 2 == 1:
            return 0

        res = 1
        l = 0

        while l < n:
            r = l
            s = 0
            while r < n and s < 2:
                if corridor[r] == 'S':
                    s += 1
                r += 1

            p = 0
            while r < n and corridor[r] == 'P':
                p += 1
                r += 1
            if r != n and p:
                res = (res * (p + 1)) % MOD
            l = r

        return res

Complexity analysis

Let n = corridor.length. Time: O(n) across the seat count and segment scan. Auxiliary space: O(1).