LeetCode Problem Workspace
Number of Ways to Divide a Long Corridor
Calculate the number of ways to split a corridor into sections with exactly two seats using dynamic programming efficiently.
3
Topics
6
Code langs
3
Related
Practice Focus
Hard · State transition dynamic programming
Answer-first summary
Calculate the number of ways to split a corridor into sections with exactly two seats using dynamic programming efficiently.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for State transition dynamic programming
This problem requires computing all valid segmentations of a corridor where each segment contains exactly two seats. Using state transition dynamic programming, we track positions of seats and calculate multiplicative ways between valid seat pairs. Early exits occur when there are fewer than two seats or the arrangement prevents exact two-seat segments.
Problem Statement
You are given a 0-indexed string corridor consisting of letters 'S' for seats and 'P' for plants. The corridor already has a room divider before the first index and after the last index, and additional dividers can be installed between positions. Your goal is to split the corridor into non-overlapping sections where each section contains exactly two seats and any number of plants.
Two ways of dividing the corridor are considered different if there exists a position where a divider is placed in one configuration but not in the other. Compute the total number of valid divisions for a given corridor string, taking care that each section strictly has two seats and accounting for all placement possibilities of additional dividers.
Examples
Example 1
Input: corridor = "SSPPSPS"
Output: 3
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
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
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 <= 105
- corridor[i] is either 'S' or 'P'.
Solution Approach
Identify seat positions
Scan the corridor string to record all indices of 'S'. If the total number of seats is odd or less than two, return 0 immediately since no valid segmentation is possible.
Compute gaps between seat pairs
Iterate over the recorded seat indices and calculate the number of plants between every consecutive seat pair that forms a valid two-seat segment. Multiply the counts of possible divider placements to track total ways.
Apply state transition DP
Use dynamic programming to maintain the number of ways to partition up to the current seat pair. For each valid segment, update the DP state by multiplying the previous count with the number of ways the segment can be divided, ensuring O(N) time and O(1) space efficiency.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | O(N) |
| Space | O(1) |
The algorithm scans the corridor once to collect seat indices and computes gaps between consecutive seat pairs. Each step involves constant-time arithmetic, resulting in O(N) time complexity. Only a few counters and the previous DP state are needed, giving O(1) space complexity.
What Interviewers Usually Probe
- Are you correctly handling cases with fewer than two seats?
- How do you efficiently count ways between consecutive two-seat segments?
- Can you optimize space usage while maintaining state transition correctness?
Common Pitfalls or Variants
Common pitfalls
- Forgetting to check for odd number of seats, which makes division impossible.
- Counting sections without exactly two seats, violating problem constraints.
- Overcomplicating DP by storing full arrays instead of using minimal state transitions.
Follow-up variants
- What if each section must contain exactly three seats instead of two?
- Allow multiple dividers between positions and count the new number of ways.
- Corridor contains additional obstacles that cannot be passed when dividing.
FAQ
What is the main strategy to solve Number of Ways to Divide a Long Corridor?
Use state transition dynamic programming by tracking seat positions and calculating ways to divide between consecutive two-seat segments.
Can I divide a corridor with only one seat?
No, at least two seats are required to form a valid section, otherwise the answer is 0.
How does GhostInterview handle large corridor strings efficiently?
It scans the corridor once and uses constant-space dynamic programming, achieving O(N) time and O(1) space.
Are sections with more than two seats allowed?
No, each section must have exactly two seats. Any deviation is invalid and excluded from counts.
How do I calculate the number of ways when multiple plant gaps exist?
Multiply the number of possible divider positions between consecutive two-seat segments to get the total number of valid arrangements.
Solution
Solution 1: Memoization Search
We design a function $\textit{dfs}(i, k)$, which represents the number of ways to partition the corridor at the $i$-th position, having already placed $k$ screens. Then the answer is $\textit{dfs}(0, 0)$.
class Solution:
def numberOfWays(self, corridor: str) -> int:
@cache
def dfs(i: int, k: int) -> int:
if i >= len(corridor):
return int(k == 2)
k += int(corridor[i] == "S")
if k > 2:
return 0
ans = dfs(i + 1, k)
if k == 2:
ans = (ans + dfs(i + 1, 0)) % mod
return ans
mod = 10**9 + 7
ans = dfs(0, 0)
dfs.cache_clear()
return ansSolution 2: Mathematics
We can divide every two seats into a group. Between two adjacent groups of seats, if the distance between the last seat of the previous group and the first seat of the next group is $x$, then there are $x$ ways to place the screen.
class Solution:
def numberOfWays(self, corridor: str) -> int:
@cache
def dfs(i: int, k: int) -> int:
if i >= len(corridor):
return int(k == 2)
k += int(corridor[i] == "S")
if k > 2:
return 0
ans = dfs(i + 1, k)
if k == 2:
ans = (ans + dfs(i + 1, 0)) % mod
return ans
mod = 10**9 + 7
ans = dfs(0, 0)
dfs.cache_clear()
return ansContinue Topic
math
Practice more edge cases under the same topic.
arrow_forwardauto_awesomeContinue Pattern
State transition dynamic programming
Expand the same solving frame across more problems.
arrow_forwardsignal_cellular_altSame Difficulty Track
Hard
Stay on this level to stabilize interview delivery.
arrow_forward