LeetCode 2147 - Number of Ways to Divide a Long Corridor

The problem presents a long corridor represented as a string, where 'S' denotes a seat and 'P' denotes a plant. The goal is to partition this corridor into sections, such that each section contains exactly two seats and any number of plants.

leetcodehardmathstringdynamic-programming

LeetCode Problem 2147

Difficulty: 🔴 Hard
Topics: Math, String, Dynamic Programming

Solution

Problem Understanding

The problem presents a long corridor represented as a string, where 'S' denotes a seat and 'P' denotes a plant. The goal is to partition this corridor into sections, such that each section contains exactly two seats and any number of plants. There are already two dividers in place: one before the first character and one after the last character. Additional dividers may be placed between any two adjacent positions, but each position can have at most one divider.

The input is a string corridor of length n where 1 <= n <= 10^5, and it consists only of 'S' and 'P'. The output is the number of ways to divide the corridor into valid sections, modulo 10^9 + 7. If no valid division exists, return 0.

Key constraints and observations include:

  1. Sections must have exactly two seats. This implies that the total number of seats must be even, otherwise it is impossible to divide the corridor.
  2. Plants do not affect the validity of a section; they only act as fillers between seats.
  3. The length of the corridor can be up to 10^5, which rules out naive recursive or combinatorial approaches that examine every possible partition.

Important edge cases include:

  • Fewer than 2 seats: impossible to form a section.
  • Odd number of seats: impossible to divide into sections of two.
  • Consecutive seats without plants in between: must carefully place dividers.
  • Corridors with many plants between seat pairs: multiple valid divider placements increase the total count.

Approaches

Brute Force Approach

A brute-force approach would involve generating all possible ways to place dividers between characters and checking whether each resulting section contains exactly two seats. For a corridor of length n, there are up to 2^(n-1) possible divider placements, which is exponential and infeasible for n = 10^5. While this approach is correct in principle, it is too slow and will not complete within any reasonable time limit.

Optimal Approach

The key insight is that a valid section is determined entirely by pairs of seats. Once the pairs of seats are identified, the number of ways to place dividers depends on the number of plants between these pairs.

The steps are as follows:

  1. Count the total number of seats. If it is odd, return 0.
  2. Identify all pairs of consecutive seats.
  3. For each gap between the end of one seat pair and the start of the next seat pair, count the number of plants. Each gap provides multiple choices for divider placement. Specifically, if there are k plants between two sections, there are k + 1 ways to place the divider.
  4. Multiply all these counts together to get the total number of ways.

This approach avoids enumerating every partition explicitly and works in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(n) Enumerate all possible divider placements and check sections
Optimal O(n) O(1) Count plants between pairs of seats and compute product of choices

Algorithm Walkthrough

  1. Initialize a counter for seats and a result variable set to 1.
  2. Traverse the corridor string. Count the total number of seats.
  3. If the total number of seats is less than 2 or odd, return 0 because it is impossible to form sections of exactly two seats.
  4. Track positions of seats while traversing. Whenever two seats are found, mark the end of a current section.
  5. Count the number of plants between the current section's end and the next section's start.
  6. For each such gap, multiply the result by (number of plants + 1) modulo 10^9 + 7.
  7. After processing all seat pairs, return the result.

Why it works: Each valid section must have exactly two seats. By considering only pairs of seats and the plants in between, we reduce the problem to counting choices of where to place dividers between sections. The multiplication reflects independent choices for each gap.

Python Solution

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        MOD = 10**9 + 7
        seats = 0
        n = len(corridor)
        for ch in corridor:
            if ch == 'S':
                seats += 1
        
        if seats == 0 or seats % 2 != 0:
            return 0
        
        result = 1
        current_seat = 0
        i = 0
        
        while i < n:
            if corridor[i] == 'S':
                current_seat += 1
                if current_seat % 2 == 0:
                    # Count plants until next 'S'
                    plants = 0
                    i += 1
                    while i < n and corridor[i] == 'P':
                        plants += 1
                        i += 1
                    if i < n:
                        result = (result * (plants + 1)) % MOD
                    continue
            i += 1
        
        return result

Implementation walkthrough:

The code first counts total seats. If the number is odd or zero, it immediately returns 0. It then traverses the corridor, counting plants between every consecutive pair of seat pairs. Each gap multiplies the total result, and the modulo is applied to prevent overflow.

Go Solution

func numberOfWays(corridor string) int {
    const MOD int = 1e9 + 7
    seats := 0
    n := len(corridor)
    
    for i := 0; i < n; i++ {
        if corridor[i] == 'S' {
            seats++
        }
    }
    
    if seats == 0 || seats % 2 != 0 {
        return 0
    }
    
    result := 1
    currentSeat := 0
    i := 0
    
    for i < n {
        if corridor[i] == 'S' {
            currentSeat++
            if currentSeat % 2 == 0 {
                plants := 0
                i++
                for i < n && corridor[i] == 'P' {
                    plants++
                    i++
                }
                if i < n {
                    result = result * (plants + 1) % MOD
                }
                continue
            }
        }
        i++
    }
    
    return result
}

Go-specific notes: The logic mirrors Python, but we explicitly declare constants and use integer arithmetic with modulo to prevent overflow. Slices and indexing are used to traverse the string.

Worked Examples

Example 1: corridor = "SSPPSPS"

Step Current Seat Count Plants in Gap Result
i=0-1 2 2 3
i=4-5 4 0 3

Answer: 3

Example 2: corridor = "PPSPSP"

Step Current Seat Count Plants in Gap Result
i=2-3 2 3 1

Answer: 1

Example 3: corridor = "S"

Seats < 2 → return 0.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single traversal of the corridor to count seats and plants
Space O(1) Constant extra space, no auxiliary data structures

The algorithm scales linearly with the corridor length, making it efficient for n = 10^5.

Test Cases

# Provided examples
assert Solution().numberOfWays("SSPPSPS") == 3  # multiple divider placements
assert Solution().numberOfWays("PPSPSP") == 1  # only one valid division
assert Solution().numberOfWays("S") == 0       # not enough seats

# Edge cases
assert Solution().numberOfWays("") == 0        # empty corridor
assert Solution().numberOfWays("PPPP") == 0    # no seats at all
assert Solution().numberOfWays("SS") == 1      # exactly two seats, no extra dividers
assert Solution().numberOfWays("SSPSS") == 2   # two gaps, 1 plant each, multiple ways
assert Solution().numberOfWays("SPPSPPSP") == 4 # complex plant distribution
Test Why
"SSPPSPS" Tests multiple divider placements
"PPSPSP" Tests single valid section without dividers
"S" Less than 2 seats → impossible
"" Empty string → edge case
"PPPP" No seats → should return 0
"SS" Minimal valid section
"SSPSS" Multiple gaps and choices
"SPPSPPSP" Complex distribution of plants between seat pairs

Edge Cases

1. No seats or fewer than 2 seats: If the corridor has no 'S' characters or only one, no valid section can exist. The solution handles this by checking seats < 2 or seats % 2 != 0 at the start and returning 0.

**2.