Number of ways to divide a long corridor

Math String Dynamic Programming

54.6% acceptance

Feb 25, 2026

1336

127

Along a long library corridor, there is a line of seats and decorative plants. You are given a 0-indexed string corridor of length n consisting of letters 'S' and 'P' where each 'S' represents a seat and each 'P' represents a plant. One room divider has already been installed to the left of index 0, and another to the right of index n - 1. Additional room dividers can be installed. For each position between indices i - 1 and i (1 <= i <= n - 1), at most one divider can be installed. Divide the corridor into non-overlapping sections, where each section has exactly two seats with any number of plants. Return the number of ways to divide the corridor. Since the answer may be very large, return it modulo 109 + 7. If there is no way, return 0.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_ways(corridor: String) -> i32 {
    const MOD: i64 = 1_000_000_007;
    let seats: Vec<usize> = corridor
      .bytes()
      .enumerate()
      .filter(|(_, b)| *b == b'S')
      .map(|(i, _)| i)
      .collect();

    let n = seats.len();
    if n == 0 || n % 2 != 0 {
      return 0;
    }

    // For each pair (seats[2i+1], seats[2i+2]), the gap is the number of positions
    // between the 2nd seat of current pair and 1st seat of next pair
    let mut result = 1i64;
    for i in (0..n - 2).step_by(2) {
      let gap = (seats[i + 2] - seats[i + 1]) as i64;
      result = result * gap % MOD;
    }
    result as i32
  }
}