Number of Ways to Divide a Long Corridor — Medium Problem & Solution

A corridor is described by a string where 'S' marks a seat and 'P' marks a plant. Walls already stand at both ends.

Difficulty: Medium
Topics: Strings, Math, Dynamic Programming
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A corridor is described by a string where 'S' marks a seat and 'P' marks a plant. Walls already stand at both ends.

Install additional walls between positions so that every resulting section contains exactly two seats. Return the number of ways to do this, modulo 10⁹ + 7. Return 0 if it cannot be done.

Example 1

Input: corridor = "SSPPSPS"
Output: 3
Explanation: The divider between the 2nd and 3rd seat may go in any of 3 gaps.

Example 2

Input: corridor = "PPSPSP"
Output: 1
Explanation: Two seats total — one section, no wall to place.

Example 3

Input: corridor = "S"
Output: 0
Explanation: An odd number of seats can never be paired up.

Constraints

n == corridor.length
1 <= n <= 10^5
corridor[i] is either 'S' or 'P'.

How to solve Number of Ways to Divide a Long Corridor

Collect the seat positions. The pairing is forced — seats 1&2, 3&4, … — so the only decisions are the divider positions. Between the 2nd seat of one pair and the 1st seat of the next there are gap legal slots, where gap is the difference of their indices. Multiply the gaps.

Approach

Record the index of every 'S'.
Return 0 if the count is 0 or odd.
For each boundary — between seats[2i-1] and seats[2i] — multiply the answer by seats[2i] - seats[2i-1].
Return the product modulo 10⁹ + 7.

Why it works

The pairing being forced is what collapses this from a DP into a product: a section with exactly two seats and sections read left to right leave no alternative grouping. The gap count is the index difference rather than the number of plants plus one, because a wall may also sit immediately after the second seat — counting slots instead of plants gets that boundary right.

Complexity

Time — O(n)
Space — O(n) for the seat list, or O(1) computing the product on the fly

Pitfalls

Zero seats is not one way — the answer is 0, since a section must hold exactly two seats.
The gap is seats[2i] - seats[2i-1], which counts the plants between them plus one.
Take the product modulo 10⁹ + 7; it grows far past 64 bits otherwise.

Reference solution

Python

def numberOfWays(corridor: str) -> int:
    MOD = 10**9 + 7
    seats = [i for i, c in enumerate(corridor) if c == "S"]
    if not seats or len(seats) % 2 != 0:
        return 0
    answer = 1
    for p in range(2, len(seats), 2):
        answer = answer * (seats[p] - seats[p - 1]) % MOD
    return answer

JavaScript

var numberOfWays = function(corridor) {
    var MOD = 1000000007;
    var seats = [];
    for (var i = 0; i < corridor.length; i++) {
        if (corridor.charAt(i) === "S") seats.push(i);
    }
    if (seats.length === 0 || seats.length % 2 !== 0) return 0;
    var answer = 1;
    for (var p = 2; p < seats.length; p += 2) {
        answer = (answer * (seats[p] - seats[p - 1])) % MOD;
    }
    return answer;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 282 strings problems · the whole catalogue