Number of Ways to Divide a Long Corridor

Hard

#1956Time: 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.1 company

Patterns

Math Dynamic Programming

Data structures

String

Companies

Zomato

Prompt

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.

Example 1:

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:

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:

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 <= 10⁵
corridor[i] is either 'S' or 'P'.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int numberOfWays(String corridor) {3        long MOD = 1_000_000_007;4        java.util.List<Integer> seatIndices = new java.util.ArrayList<>();5        for (int i = 0; i < corridor.length(); i++) {6            if (corridor.charAt(i) == 'S') {7                seatIndices.add(i);8            }9        }10 11        int numSeats = seatIndices.size();12        if (numSeats == 0 || numSeats % 2 != 0) {13            return 0;14        }15 16        long ways = 1;17        // We are interested in the gaps between pairs of seats.18        // The first gap is between the 2nd and 3rd seats.19        // The second gap is between the 4th and 5th seats, and so on.20        for (int i = 2; i < numSeats; i += 2) {21            int prevSeatIndex = seatIndices.get(i - 1);22            int currSeatIndex = seatIndices.get(i);23            long diff = currSeatIndex - prevSeatIndex;24            ways = (ways * diff) % MOD;25        }26 27        return (int) ways;28    }29}

Complexity

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.

Trade-offs

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).

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.

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.

Walkthrough

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.

1class Solution {2    public int numberOfWays(String corridor) {3        long MOD = 1_000_000_007;4        long ways = 1;5        int seatCount = 0;6        int prevSeatIndex = -1;7 8        for (int i = 0; i < corridor.length(); i++) {9            if (corridor.charAt(i) == 'S') {10                seatCount++;11                if (seatCount >= 2 && seatCount % 2 == 1) {12                    // This is the 3rd, 5th, 7th, etc., seat.13                    // It marks the start of a new section.14                    // The gap is between this seat and the previous one.15                    long diff = i - prevSeatIndex;16                    ways = (ways * diff) % MOD;17                }18                prevSeatIndex = i;19            }20        }21 22        if (seatCount == 0 || seatCount % 2 != 0) {23            return 0;24        }25 26        return (int) ways;27    }28}

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.

Trade-offs

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.

Solutions

Solution

1class Solution {2private3  String s;4private5  int n;6private7  int[][] f;8private9  static final int MOD = (int)1 e9 + 7;10public11  int numberOfWays(String corridor) {12    s = corridor;13    n = s.length();14    f = new int[n][3];15    for (var e : f) {16      Arrays.fill(e, -1);17    }18    return dfs(0, 0);19  }20private21  int dfs(int i, int cnt) {22    if (i == n) {23      return cnt == 2 ? 1 : 0;24    }25    cnt += s.charAt(i) == 'S' ? 1 : 0;26    if (cnt > 2) {27      return 0;28    }29    if (f[i][cnt] != -1) {30      return f[i][cnt];31    }32    int ans = dfs(i + 1, cnt);33    if (cnt == 2) {34      ans += dfs(i + 1, 0);35      ans %= MOD;36    }37    f[i][cnt] = ans;38    return ans;39  }40}

1class Solution {2public:3  const int mod = 1e9 + 7;4  int numberOfWays(string corridor) {5    int n = corridor.size();6    vector<vector<int>> f(n, vector<int>(3, -1));7    function<int(int, int)> dfs;8    dfs = [&](int i, int cnt) {9      if (i == n)10        return cnt == 2 ? 1 : 0;11      cnt += corridor[i] == 'S';12      if (cnt > 2)13        return 0;14      if (f[i][cnt] != -1)15        return f[i][cnt];16      int ans = dfs(i + 1, cnt);17      if (cnt == 2) {18        ans += dfs(i + 1, 0);19        ans %= mod;20      }21      f[i][cnt] = ans;22      return ans;23    };24    return dfs(0, 0);25  }26};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem