# Number of Ways to Divide a Long Corridor
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-ways-to-divide-a-long-corridor)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-divide-a-long-corridor
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** String
**Companies:** [Zomato](https://scaleengineer.com/companies/zomato)
---
## 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** `109 + 7`. If there is no way, return `0`.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-ways-to-divide-a-long-corridor/image0.png) 

**Input:** corridor = "SSPPSPS"
**Output:** 3
**Explanation:** There are 3 different ways to divide the corridor.
The black bars in the above image indicate the two room dividers already installed.
Note that in each of the ways, **each** section has exactly **two** seats.

**Example 2:**

![](https://assets.glich.co/dsa/number-of-ways-to-divide-a-long-corridor/image1.png) 

**Input:** corridor = "PPSPSP"
**Output:** 1
**Explanation:** There is only 1 way to divide the corridor, by not installing any additional dividers.
Installing any would create some section that does not have exactly two seats.

**Example 3:**

![](https://assets.glich.co/dsa/number-of-ways-to-divide-a-long-corridor/image2.png) 

**Input:** corridor = "S"
**Output:** 0
**Explanation:** There is no way to divide the corridor because there will always be a section that does not have exactly two seats.

**Constraints:**

* `n == corridor.length`
* `1 <= n <= 105`
* `corridor[i]` is either `'S'` or `'P'`.

# Approaches
## Two-Pass Approach using Seat Indices
This approach involves two main steps. First, we iterate through the entire corridor to identify and store the indices of all seats ('S'). After collecting all seat indices, we perform a second pass on this list of indices to calculate the number of ways to place dividers.
**Time:** O(N), where N is the length of the corridor. The first pass to find seats takes O(N), and the second pass over the seat indices takes O(S) where S is the number of seats (S <= N). · **Space:** O(S), which can be up to O(N) in the worst case where most or all characters are seats. This is for storing the `seatIndices` list.
**Pros:** The logic is straightforward and easy to understand.; It correctly solves the problem by identifying the core constraint on divider placement.
**Cons:** Requires extra space to store the indices of all seats, which can be up to O(N) in the worst case.; It requires two passes over the data (one over the string, one over the list of indices).
### Explanation
The core idea is that dividers can only be placed between pairs of seats. For a valid division, the corridor must be partitioned into sections each containing exactly two seats. This implies that the total number of seats must be an even number and greater than zero.

We first scan the `corridor` string and store the indices of every 'S' in a list. If the total count of seats is zero or odd, no valid division is possible, so we return 0.

If the count is valid, we know that the first section must contain the first two seats, the second section must contain the third and fourth seats, and so on. A divider must be placed between the second seat of one section and the first seat of the next. For example, between the 2nd and 3rd seats, between the 4th and 5th seats, etc.

The number of ways to place a divider between the `i`-th pair and the `(i+1)`-th pair is the number of available slots between the second seat of the `i`-th pair and the first seat of the `(i+1)`-th pair. This is equal to the difference in their indices.

We calculate the total number of ways by multiplying the number of choices for each required divider, as these choices are independent. The final result is taken modulo `10^9 + 7`.

```java
class Solution {
    public int numberOfWays(String corridor) {
        long MOD = 1_000_000_007;
        java.util.List<Integer> seatIndices = new java.util.ArrayList<>();
        for (int i = 0; i < corridor.length(); i++) {
            if (corridor.charAt(i) == 'S') {
                seatIndices.add(i);
            }
        }

        int numSeats = seatIndices.size();
        if (numSeats == 0 || numSeats % 2 != 0) {
            return 0;
        }

        long ways = 1;
        // We are interested in the gaps between pairs of seats.
        // The first gap is between the 2nd and 3rd seats.
        // The second gap is between the 4th and 5th seats, and so on.
        for (int i = 2; i < numSeats; i += 2) {
            int prevSeatIndex = seatIndices.get(i - 1);
            int currSeatIndex = seatIndices.get(i);
            long diff = currSeatIndex - prevSeatIndex;
            ways = (ways * diff) % MOD;
        }

        return (int) ways;
    }
}
```
### Algorithm
- Create a list, `seatIndices`, to store the 0-based index of each seat 'S'.
- Iterate through the input `corridor` string. If `corridor[i]` is 'S', add `i` to `seatIndices`.
- Check the size of `seatIndices`. If it's 0 or an odd number, return 0, as no valid division is possible.
- Initialize a `long` variable `ways` to 1 and `MOD = 1_000_000_007`.
- Iterate through `seatIndices` from the 3rd seat (`i = 2`) to the end, with a step of 2. In each step, we are looking at the gap between a pair of seats, e.g., between the 2nd and 3rd, 4th and 5th, and so on.
- For each `i`, calculate the number of divider placements available between the previous pair and the current pair. This is `seatIndices.get(i) - seatIndices.get(i-1)`.
- Multiply `ways` by this difference and take the modulo `MOD`: `ways = (ways * (seatIndices.get(i) - seatIndices.get(i-1))) % MOD;`
- Return `(int) ways`.

## Optimized One-Pass Approach with Constant Space
This approach improves upon the previous one by processing the corridor in a single pass and using only a few variables to keep track of the state, thus achieving constant space complexity.
**Time:** O(N), as we iterate through the string once. · **Space:** O(1), as we only use a few variables to store the state, regardless of the input size.
**Pros:** Highly efficient in both time and space.; Processes the input in a single pass.; Uses constant extra space, making it suitable for very large inputs.
**Cons:** The logic might be slightly less intuitive at first glance compared to the two-pass approach.
### Explanation
Instead of storing all seat indices, we can calculate the number of ways on the fly. We iterate through the corridor, keeping a count of the seats encountered so far.

The key insight remains the same: the number of ways is the product of the number of possible divider positions between consecutive pairs of seats. A choice for a divider position arises only after we have found a complete pair of seats and are about to start a new pair. This happens when we encounter the 3rd, 5th, 7th, etc., seat.

We use a variable `seatCount` to track the number of seats seen. We also need `prevSeatIndex` to remember the index of the previously seen seat.

When we find a seat `S`:
- We increment `seatCount`.
- If `seatCount` becomes odd and is greater than 2 (e.g., 3, 5, ...), it means we've just started a new pair. The previous seat (at `prevSeatIndex`) was the end of the last pair. The number of ways to place a divider between them is `currentIndex - prevSeatIndex`. We multiply our total `ways` by this value.
- We then update `prevSeatIndex` to the current seat's index.

After the loop, we must check if the total `seatCount` is valid (even and non-zero). If not, the answer is 0.

```java
class Solution {
    public int numberOfWays(String corridor) {
        long MOD = 1_000_000_007;
        long ways = 1;
        int seatCount = 0;
        int prevSeatIndex = -1;

        for (int i = 0; i < corridor.length(); i++) {
            if (corridor.charAt(i) == 'S') {
                seatCount++;
                if (seatCount >= 2 && seatCount % 2 == 1) {
                    // This is the 3rd, 5th, 7th, etc., seat.
                    // It marks the start of a new section.
                    // The gap is between this seat and the previous one.
                    long diff = i - prevSeatIndex;
                    ways = (ways * diff) % MOD;
                }
                prevSeatIndex = i;
            }
        }

        if (seatCount == 0 || seatCount % 2 != 0) {
            return 0;
        }

        return (int) ways;
    }
}
```
### Algorithm
- Initialize `seatCount = 0`, `ways = 1L`, and `prevSeatIndex = -1`. Define `MOD = 1_000_000_007`.
- Iterate through the `corridor` string from left to right with index `i`.
- If `corridor.charAt(i) == 'S'`:
    - Increment `seatCount`.
    - If `seatCount` is odd and greater than or equal to 3, it marks the beginning of a new pair. The gap for a divider is between this seat and the previous one.
    - Calculate the difference: `diff = i - prevSeatIndex`.
    - Update `ways`: `ways = (ways * diff) % MOD`.
    - Update `prevSeatIndex` to the current index `i`.
- After the loop, if `seatCount` is 0 or odd, return 0.
- Otherwise, return `(int) ways`.

# Solutions
### Java

```java
class Solution {
private
  String s;
private
  int n;
private
  int[][] f;
private
  static final int MOD = (int)1 e9 + 7;
public
  int numberOfWays(String corridor) {
    s = corridor;
    n = s.length();
    f = new int[n][3];
    for (var e : f) {
      Arrays.fill(e, -1);
    }
    return dfs(0, 0);
  }
private
  int dfs(int i, int cnt) {
    if (i == n) {
      return cnt == 2 ? 1 : 0;
    }
    cnt += s.charAt(i) == 'S' ? 1 : 0;
    if (cnt > 2) {
      return 0;
    }
    if (f[i][cnt] != -1) {
      return f[i][cnt];
    }
    int ans = dfs(i + 1, cnt);
    if (cnt == 2) {
      ans += dfs(i + 1, 0);
      ans %= MOD;
    }
    f[i][cnt] = ans;
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  const int mod = 1e9 + 7;
  int numberOfWays(string corridor) {
    int n = corridor.size();
    vector<vector<int>> f(n, vector<int>(3, -1));
    function<int(int, int)> dfs;
    dfs = [&](int i, int cnt) {
      if (i == n)
        return cnt == 2 ? 1 : 0;
      cnt += corridor[i] == 'S';
      if (cnt > 2)
        return 0;
      if (f[i][cnt] != -1)
        return f[i][cnt];
      int ans = dfs(i + 1, cnt);
      if (cnt == 2) {
        ans += dfs(i + 1, 0);
        ans %= mod;
      }
      f[i][cnt] = ans;
      return ans;
    };
    return dfs(0, 0);
  }
};

```

### Python

```python
class Solution:
    def numberOfWays(self, corridor: str) -> int: @ cache def dfs(i, cnt): if i == n: return int(cnt == 2) cnt += corridor[i] == 'S' if cnt > 2: return 0 ans = dfs(i + 1, cnt) if cnt == 2: ans += dfs(i + 1, 0) ans %= mod return ans n = len(corridor) mod = 10 ** 9 + 7 ans = dfs(0, 0) dfs . cache_clear() return ans

```