Number of Ways to Divide a Long Corridor — Solution
Number of Ways to Divide a Long Corridor solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Number of Ways to Divide a Long Corridor is a medium coding problem on strings, dynamic programming and math, asked in Amazon, Google, Microsoft and Zomato interviews.
- Difficulty: Medium
- Topics: Strings, Dynamic Programming, Math
- Asked at: Amazon, Google, Microsoft, Zomato
- 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.length1 <= n <= 10^5corridor[i] is either 'S' or 'P'.
Hints for Number of Ways to Divide a Long Corridor
Hint 1
If the number of seats is zero or odd, the answer is 0.
Hint 2
The seats pair up in order: 1st with 2nd, 3rd with 4th, and so on — there is no choice about which seats share a section.
Hint 3
The only freedom is where each divider sits, between the end of one pair and the start of the next.
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]andseats[2i]— multiply the answer byseats[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 answerJava
public static int numberOfWays(String corridor) {
final long MOD = 1000000007L;
List<Integer> seats = new ArrayList<>();
for (int i = 0; i < corridor.length(); i++) {
if (corridor.charAt(i) == 'S') seats.add(i);
}
if (seats.isEmpty() || seats.size() % 2 != 0) return 0;
long answer = 1;
for (int p = 2; p < seats.size(); p += 2) {
answer = answer * (seats.get(p) - seats.get(p - 1)) % MOD;
}
return (int) answer;
}C++
int numberOfWays(string corridor) {
const long long MOD = 1000000007LL;
vector<int> seats;
for (int i = 0; i < (int) corridor.size(); i++) {
if (corridor[i] == 'S') seats.push_back(i);
}
if (seats.empty() || seats.size() % 2 != 0) return 0;
long long answer = 1;
for (size_t p = 2; p < seats.size(); p += 2) {
answer = answer * (seats[p] - seats[p - 1]) % MOD;
}
return (int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Dynamic Programming