2147. Number of Ways to Divide a Long Corridor Hard

1/**
2 * [2147] Number of Ways to Divide a Long Corridor
3 *
4 * 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.
5 * 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.
6 * 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.
7 * Return the number of ways to divide the corridor. Since the answer may be very large, return it modulo 10^9 + 7. If there is no way, return 0.
8 *  
9 * Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/04/1.png" style="width: 410px; height: 199px;" />
11 * Input: corridor = "SSPPSPS"
12 * Output: 3
13 * Explanation: There are 3 different ways to divide the corridor.
14 * The black bars in the above image indicate the two room dividers already installed.
15 * Note that in each of the ways, each section has exactly two seats.
16 * 
17 * Example 2:
18 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/04/2.png" style="width: 357px; height: 68px;" />
19 * Input: corridor = "PPSPSP"
20 * Output: 1
21 * Explanation: There is only 1 way to divide the corridor, by not installing any additional dividers.
22 * Installing any would create some section that does not have exactly two seats.
23 * 
24 * Example 3:
25 * <img alt="" src="https://assets.leetcode.com/uploads/2021/12/12/3.png" style="width: 115px; height: 68px;" />
26 * Input: corridor = "S"
27 * Output: 0
28 * Explanation: There is no way to divide the corridor because there will always be a section that does not have exactly two seats.
29 * 
30 *  
31 * Constraints:
32 * 
33 * 	n == corridor.length
34 * 	1 <= n <= 10^5
35 * 	corridor[i] is either 'S' or 'P'.
36 * 
37 */
38pub struct Solution {}
39
40// problem: https://leetcode.com/problems/number-of-ways-to-divide-a-long-corridor/
41// discuss: https://leetcode.com/problems/number-of-ways-to-divide-a-long-corridor/discuss/?currentPage=1&orderBy=most_votes&query=
42
43// submission codes start here
44
45impl Solution {
46    pub fn number_of_ways(corridor: String) -> i32 {
47        0
48    }
49}
50
51// submission codes end
52
53#[cfg(test)]
54mod tests {
55    use super::*;
56
57    #[test]
58    fn test_2147() {
59    }
60}
61