Formatted question description: https://leetcode.ca/all/2147.html

# 2147. Number of Ways to Divide a Long Corridor (Hard)

Along a long library corridor, there is a line of seats and decorative plants. You are given a **0-indexed** string `corridor`

of length `n`

consisting of letters `'S'`

and `'P'`

where each `'S'`

represents a seat and each `'P'`

represents a plant.

One room divider has **already** been installed to the left of index `0`

, and **another** to the right of index `n - 1`

. Additional room dividers can be installed. For each position between indices `i - 1`

and `i`

(`1 <= i <= n - 1`

), at most one divider can be installed.

Divide the corridor into non-overlapping sections, where each section has **exactly two seats** with any number of plants. There may be multiple ways to perform the division. Two ways are **different** if there is a position with a room divider installed in the first way but not in the second way.

Return *the number of ways to divide the corridor*. Since the answer may be very large, return it **modulo** `10`

. If there is no way, return ^{9} + 7`0`

.

**Example 1:**

Input:corridor = "SSPPSPS"Output:3Explanation:There are 3 different ways to divide the corridor. The black bars in the above image indicate the two room dividers already installed. Note that in each of the ways,eachsection has exactlytwoseats.

**Example 2:**

Input:corridor = "PPSPSP"Output:1Explanation:There is only 1 way to divide the corridor, by not installing any additional dividers. Installing any would create some section that does not have exactly two seats.

**Example 3:**

Input:corridor = "S"Output:0Explanation:There is no way to divide the corridor because there will always be a section that does not have exactly two seats.

**Constraints:**

`n == corridor.length`

`1 <= n <= 10`

^{5}`corridor[i]`

is either`'S'`

or`'P'`

.

**Similar Questions**:

- Decode Ways II (Hard)
- Minimum Cost to Cut a Stick (Hard)
- Ways to Split Array Into Three Subarrays (Medium)

## Solution 1.

**Intuition**: If there are `p`

plants between two sections, we multiply the answer by `p + 1`

.

**Algorithm**:

If the total number of seats is not a positive even number, return 0

Scan `corridor`

section by section, count the number of plants between sections, and multiply the answer by `plant + 1`

.

```
// OJ: https://leetcode.com/problems/number-of-ways-to-divide-a-long-corridor/
// Time: O(N)
// Space: O(1)
class Solution {
public:
int numberOfWays(string s) {
long ans = 1, mod = 1e9 + 7, N = s.size(), total = 0, section = 0;
for (int i = 0; i < N; ) {
int seat = 0, plant = 0;
for (; i < N && seat < 2; ++i) {
seat += s[i] == 'S';
if (seat == 0) plant += s[i] == 'P'; // Only count the plants in the front of the first seat of this section
}
if (seat && section++ > 0) ans = ans * (plant + 1) % mod;
total += seat;
}
return total % 2 == 0 && total ? ans : 0; // if the total number of seats is not a positive even number, return 0
}
};
```

## Discuss

https://leetcode.com/problems/number-of-ways-to-divide-a-long-corridor/discuss/1709665/C%2B%2B-Scan-section-by-section-O(N)-Time-O(1)-space