#2147
Number of Ways to Divide a Long Corridor
candidate master · 1310 · lc hard +32 · verified · 54.6% accepted · 1,336 likes · top 47%
Description
A long library corridor contains a line of seats ('S') and decorative plants ('P'). You are given a 0-indexed string corridor of length n.
Two dividers are already installed at the far left (before index 0) and far right (after index n - 1). Additional dividers may be placed at any position between adjacent indices (at most one per gap).
Partition the corridor into non-overlapping sections so that each section contains exactly two seats and any number of plants. Count the number of distinct ways to do this.
Return the answer modulo 109 + 7. If no valid partition exists, return 0.
Example 1:
Input: corridor = "SSPPSPS"
Output: 3
Explanation: 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, each section has exactly two seats.
Example 2:
Input: corridor = "PPSPSP"
Output: 1
Explanation: 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: 0
Explanation: There is no way to divide the corridor because there will always be a section that does not have exactly two seats.
Code
1
2
3