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.
1public class CorridorDivider {
2
The Java solution leverages the same principle of scanning and counting, using long for the multiplication to avoid overflow and mod to control large numbers.