NeetCode #704LC-2147Hard1-D Dynamic Programming
← Back to All Problems#704 · #2147 · Number of Ways to Divide a Long Corridor(分隔长廊的方案数)
📌 Problem Statement & Constraints
Given a corridor string
corridor made of S (seat) and P (plant), place dividers on plants to split the corridor into sections that each contain exactly two seats. Count the number of ways, modulo 10^9 + 7. Constraints: 1 <= corridor.length <= 10^5, and corridor consists only of S and P.💡 Core Algorithmic Approaches
- If the total number of seats is zero or odd, no valid division exists, so return 0.
- A divider may sit only on a plant, and only between the second seat of one section and the first seat of the next.
- Between those two boundary seats there are
gconsecutive plants, and the divider may occupy any of theg + 1slots around them. - Multiply the
g + 1factors over all section boundaries.
💻 Benchmark Python3 Implementation
class Solution:
def numberOfWays(self, corridor: str) -> int:
MOD = 10 ** 9 + 7
seats = [i for i, ch in enumerate(corridor) if ch == "S"]
if not seats or len(seats) % 2:
return 0
ways = 1
for k in range(2, len(seats), 2):
gap = seats[k] - seats[k - 1] # plants between the boundary seats
ways = ways * gap % MOD
return ways⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass to collect seat indices and one pass over the seats.
💾 Space Complexity
O(number of seats): the index list.
⚠️ Interview Pitfalls & Follow-ups
- Returning 1 when there are no seats: a corridor with zero seats has no valid two-seat sections, so the answer is 0.
- Counting
gapinstead ofgap + 1: the divider may occupy any of thegap + 1slots between the two boundary seats. - Allowing a divider adjacent to a seat: sections must contain exactly two seats, so dividers go only strictly between seat pairs.
- Skipping the odd-seat check: an odd total can never be partitioned into pairs.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.