⚡Flashcard Drill➔
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

  1. If the total number of seats is zero or odd, no valid division exists, so return 0.
  2. A divider may sit only on a plant, and only between the second seat of one section and the first seat of the next.
  3. Between those two boundary seats there are g consecutive plants, and the divider may occupy any of the g + 1 slots around them.
  4. Multiply the g + 1 factors 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 gap instead of gap + 1: the divider may occupy any of the gap + 1 slots 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems