Sponsored
Sponsored
This approach involves counting the total number of 'S' in the string. We need to ensure that the total number of seats is even, as every section must have exactly two seats. If the count of 'S' is not even or less than two, return 0 because no valid sections can be formed.
Initialize a counter for seats and iterate through the corridor. Each time you encounter the second seat in a pair, check how many plants were between this second seat and the previous pair of seats. The count of positions (plants) between these pairs is the spot where dividers can be placed. Compute the total number of ways combine these choices.
Time Complexity: O(n), where n is the length of the corridor string because it processes the string in a single pass.
Space Complexity: O(1), since it uses a fixed amount of extra space for variables.
1function numberOfWays(corridor) {
2 const MOD = 1e9 + 7;
3 let seatCount = 0;
4 for (let char of corridor) {
5 if (char === 'S') seatCount++;
6 }
7 if (seatCount % 2 !== 0 || seatCount < 2) return 0;
8
9 let ways = 1,
10 plantsBetween = 0,
11 foundFirstPair = false,
12 currentSeats = 0;
13
14 for (let char of corridor) {
15 if (char === 'S') {
16 currentSeats++;
17 if (currentSeats === 2) {
18 if (foundFirstPair) {
19 ways = (ways * (plantsBetween + 1)) % MOD;
20 }
21 plantsBetween = 0;
22 foundFirstPair = true;
23 currentSeats = 0;
24 }
25 } else if (foundFirstPair) {
26 plantsBetween++;
27 }
28 }
29 return ways;
30}This function checks the balance of seats first and iterates through the corridor string, finding the spots between every second pair of seats where dividers can be placed, multiplying the number of options as it goes.
The two-pointer technique helps efficiently track the segments of the corridor. Position both pointers initially at the start of the string. Move the first pointer until two 'S' characters are found, marking the start of a section. Move the second pointer to continue finding the next two 'S' for another section.
Each transition between segments of groups discovered by the pointers represents a potential divider placement, and the number of these potential movements gives the number of possible configurations.
Time Complexity: O(n) due to the string being processed a single time.
Space Complexity: O(1), since only a fixed number of state-tracking variables are used.
1#include <iostream>
2#include <string>
3
4int numberOfWays(const std::string& corridor) {
const int MOD = 1e9 + 7;
int seat_count = 0;
for (char c : corridor) {
if (c == 'S') seat_count++;
}
if (seat_count % 2 != 0 || seat_count < 2) return 0;
int ways = 1, plants_between = 0;
bool first_pair_found = false;
int current_seats = 0;
for (char c : corridor) {
if (c == 'S') {
current_seats++;
if (current_seats == 2) {
if (first_pair_found) {
ways = static_cast<long long>(ways) * (plants_between + 1) % MOD;
}
plants_between = 0;
first_pair_found = true;
current_seats = 0;
}
} else if (first_pair_found) {
plants_between++;
}
}
return ways;
}
int main() {
std::string corridor = "SSPPSPS";
std::cout << numberOfWays(corridor) << std::endl;
return 0;
}This program approaches the corridor string in one pass, using a variable to determine when to apply the mod operation for calculating potential dividers and calculates the result in a manner similar to counting plants between seat pairs.