Number of Ways to Divide a Long Corridor - Practice Coding Problems

Number of Ways to Divide a Long Corridor - Problem

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. There may be multiple ways to perform the division. Two ways are different if there is a position with a room divider installed in the first way but not in the second way.

Return the number of ways to divide the corridor. Since the answer may be very large, return it modulo 10⁹ + 7. If there is no way, return 0.

Input & Output

Example 1 — Basic Case

$ Input: corridor = "SSPPSPS"

› Output: 3

💡 Note: 6 seats total (even ✓). Seats at positions [0,1,3,4,6]. Pairs: (0,1), (3,4), (6). Gap between pairs: positions 2-3 gives 2 options, position 5-6 gives 1 option. Total: 2 × 1 = 2. Wait, let me recalculate... Actually 3 ways total.

Example 2 — No Valid Division

$ Input: corridor = "PPSPPP"

› Output: 0

💡 Note: Only 1 seat total (odd number), impossible to create sections with exactly 2 seats each.

Example 3 — Minimum Valid Case

$ Input: corridor = "SS"

› Output: 1

💡 Note: Exactly 2 seats, only one way to divide: both seats in one section.

Constraints

1 ≤ corridor.length ≤ 10⁵
corridor[i] is either 'S' or 'P'

Visualization

Tap to expand

Understanding the Visualization

Input

Corridor string with seats (S) and plants (P)

Process

Find seat positions and group into pairs

Output

Count ways to place dividers between pairs

Key Takeaway

🎯 Key Insight: The number of ways equals the product of gap sizes between consecutive seat-pairs

Asked in

G Google 25 f Facebook 18 M Microsoft 15 a Amazon 12

The key insight is recognizing this as a combinatorial problem. We must group seats into pairs, then count the ways to place dividers between consecutive pairs. The mathematical pattern approach finds seat positions and multiplies the gap sizes between consecutive seat-pairs. Time: O(n), Space: O(k) where k is number of seats.

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Pattern Recognition	O(n)	O(k)	Find seat pairs and multiply gap choices between them
Brute Force Recursion	O(2ⁿ)	O(n)	Try all possible divider placements recursively

Mathematical Pattern Recognition — Algorithm Steps

Count total seats - return 0 if odd or zero
Find all seat positions
Group seats into pairs
Count plants between consecutive pairs
Multiply all gap counts

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Seats

Locate all seat positions in the corridor

Group Pairs

Group consecutive seats into pairs of 2

Count Gaps

Multiply gap sizes between pairs for total ways

Code -

solution.c — C

#include <stdio.h>
#include <string.h>

const int MOD = 1000000007;

int solution(char* corridor) {
    int len = strlen(corridor);
    int seats[len];
    int seatCount = 0;
    
    // Find all seat positions
    for (int i = 0; i < len; i++) {
        if (corridor[i] == 'S') {
            seats[seatCount++] = i;
        }
    }
    
    // Check if division is possible
    if (seatCount == 0 || seatCount % 2 != 0) {
        return 0;
    }
    
    if (seatCount == 2) {
        return 1;
    }
    
    long long result = 1;
    // For each pair of consecutive seat pairs, count gap between them
    for (int i = 2; i < seatCount; i += 2) {
        long long gap = seats[i] - seats[i-1];
        result = (result * gap) % MOD;
    }
    
    return result;
}

int main() {
    char corridor[100001];
    fgets(corridor, sizeof(corridor), stdin);
    corridor[strcspn(corridor, "\n")] = 0;
    
    printf("%d\n", solution(corridor));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the corridor to find seats and count gaps

✓ Linear Growth

Space Complexity

O(k)

Store seat positions where k is number of seats

✓ Linear Space

28.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Pattern Recognition — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler