Number of Ways to Divide a Long Corridor

hard combinatorics counting string

Problem

A corridor is a string of seats ('S') and plants ('P'). Dividers already sit just left of index 0 and just right of the last index; you may add more dividers between adjacent positions. Split the corridor into non-overlapping sections so that each section has exactly two seats (and any number of plants). Return the number of distinct ways, modulo 10⁹+7; return 0 if it is impossible.

Inputcorridor = "SSPPSPS"

Output3

The 2nd and 3rd seats sit at indices 1 and 4, so the divider between the two sections has 4 − 1 = 3 legal positions.

Inputcorridor = "PPSPSP"

Output1

Only 2 seats total, adjacent — the single section is forced, so exactly 1 way.

corridor (S and P only)

def number_of_ways(corridor):
    MOD = 10**9 + 7
    seats = 0
    ways = 1
    prev_end = -1
    for i, ch in enumerate(corridor):
        if ch != 'S':
            continue
        seats += 1
        if seats % 2 == 1 and seats > 1:
            ways = ways * (i - prev_end) % MOD
        if seats % 2 == 0:
            prev_end = i
    if seats == 0 or seats % 2 == 1:
        return 0
    return ways

function numberOfWays(corridor) {
  const MOD = 1000000007n;
  let seats = 0, prevEnd = -1;
  let ways = 1n;
  for (let i = 0; i < corridor.length; i++) {
    if (corridor[i] !== 'S') continue;
    seats++;
    if (seats % 2 === 1 && seats > 1) {
      ways = (ways * BigInt(i - prevEnd)) % MOD;
    }
    if (seats % 2 === 0) prevEnd = i;
  }
  if (seats === 0 || seats % 2 === 1) return 0;
  return Number(ways);
}

int numberOfWays(String corridor) {
    long MOD = 1_000_000_007L;
    long seats = 0, ways = 1;
    int prevEnd = -1;
    for (int i = 0; i < corridor.length(); i++) {
        if (corridor.charAt(i) != 'S') continue;
        seats++;
        if (seats % 2 == 1 && seats > 1) {
            ways = ways * (i - prevEnd) % MOD;
        }
        if (seats % 2 == 0) prevEnd = i;
    }
    if (seats == 0 || seats % 2 == 1) return 0;
    return (int) ways;
}

int numberOfWays(string corridor) {
    const long long MOD = 1000000007LL;
    long long seats = 0, ways = 1;
    int prevEnd = -1;
    for (int i = 0; i < (int) corridor.size(); i++) {
        if (corridor[i] != 'S') continue;
        seats++;
        if (seats % 2 == 1 && seats > 1) {
            ways = ways * (i - prevEnd) % MOD;
        }
        if (seats % 2 == 0) prevEnd = i;
    }
    if (seats == 0 || seats % 2 == 1) return 0;
    return (int) ways;
}

Explanation

Every valid section contains exactly two seats. So if we list the seats in order, they must pair up: seats 1 and 2 form the first section, seats 3 and 4 the second, and so on. This immediately forces the total seat count to be a positive even number — otherwise the answer is 0.

The only freedom is where the divider between two consecutive sections goes. That divider sits somewhere between the seat that closed the previous pair (call its index prevEnd) and the seat that opens the next pair (at index i). Every position from just after prevEnd up to just before i is legal, and there are exactly i − prevEnd of them — that index difference already includes the plant slots and the slot immediately before the new seat.

So we scan once, counting seats and remembering prevEnd. When a seat makes the count odd and greater than one, it opens a new pair, so we multiply the running answer by i − prevEnd. Whenever a seat makes the count even, it closes a pair, so we update prevEnd = i. The first pair needs no multiply because its left divider is the fixed one at the corridor's start.

The boundaries are independent, so their slot counts multiply. Because the product can be enormous, we keep it modulo 10⁹+7.

Example "SSPPSPS": seats arrive at indices 0,1,4,6. Seat 2 (index 1) closes pair 1, so prevEnd = 1. Seat 3 (index 4) opens pair 2, multiplying by 4 − 1 = 3. With 4 seats (even), the answer is 1 × 3 = 3.

Time: O(n) Space: O(1)