2147. Number of Ways to Divide a Long Corridor

Problem Description

The corridor in the library has a number of seats and decorative plants arranged in a line. This arrangement is represented as a string corridor where the character 'S' represents a seat and 'P' represents a plant. There's already one room divider at each end of the corridor. Our goal is to add more dividers in between elements of the corridor so we can divide the corridor into sections. Each section must contain exactly two seats. There is no constraint on the number of plants a section can have. We have to find the total number of different ways we can add dividers to achieve this. Two ways of adding dividers are considered different if the position of any divider is different between the two. The final answer needs to be returned as a modulo of 10^9 + 7. If it is not possible to divide the corridor according to the given rules, we must return 0.

Intuition

To solve this problem, we adopt a recursive approach with memoization, commonly known as dynamic programming. The intuition here is that if we encounter a seat ('S'), we track it. If by adding this seat, we form a pair of seats (meaning we have encountered two seats so far), we have two choices: either put a divider right after this pair of seats or move to the next symbol in the corridor. If we decide to put a divider, we reset our seat count to start forming new sections. If we come across a plant (’P’), it doesn't affect the count of the seats but we still move forward making further recursive calls.

We use the dfs function which is defined as dfs(i, cnt). Here i is the current position in the corridor string and cnt is the current count of seats we've encountered so far without hitting a pair. If cnt exceeds two we return 0 since any section having more than two seats is invalid. When i reaches the end of the corridor and we have exactly two seats in the current section (cnt == 2), this is one valid way so we return 1. Otherwise, we return 0 since it's an incomplete or invalid state.

We continue this recursive approach until we've explored all possibilities. To speed up the process, we use memoization (@cache decorator) to remember results of subproblems that we have already solved to avoid redundant calculations.

Each time we have a pair of seats, we can add the current number of ways to the final answer since it represents a branching point where we can make a choice to add or not add a divider. The final answer could be very large, hence we use modulo operation with 10^9 + 7 to keep our final count within integer limits.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The solution to the problem employs recursive depth-first search (DFS) with memoization, a common dynamic programming technique, to explore all the possible ways to divide the corridor while ensuring the business rule of exactly two seats per section is met. The code defines a helper function dfs(i, cnt) which uses the following approach:

Base Case: When the recursion reaches the end of the string (i.e., i == n), it checks if the count of seats cnt is exactly 2. If it is, it returns 1, indicating one valid division is found. Otherwise, it returns 0.
Seat Counting: It increments the count cnt if the current character is a seat ('S'). If this count goes above 2, it returns 0 immediately, as more than two seats would violate the corridor division rule.
Recursion: There are two recursive calls within the dfs function:
- The first call, dfs(i + 1, cnt), is made to explore the possibility of not placing a divider after the current index, regardless of how many seats have been seen so far (as long as it's not more than two).
- The second call, dfs(i + 1, 0), is made only when cnt is exactly 2, indicating that a section with two seats has been completed, and a divider may be installed here. This recursive call starts the count over from zero for the next section.
Memoization: The @cache decorator is used above the dfs function to memoize the results. This ensures that once a particular state (i, cnt) has been computed, it will not be computed again, which significantly reduces the number of calculations.
Modulo Operation: The result of each recursive call (if a divider is placed) is taken modulo 10^9 + 7. This is done because the final answer may be very large, and we want to avoid integer overflow by keeping the number within the specified limits.
Combination Summation: The function dfs keeps a running total of valid ways to divide the corridor as it recursively explores each possibility. Every time a section completes with two seats, it adds to the possible combinations and continues to the next recursive case.

The main function initializes the required parameters (such as the length of the corridor n and the modulo mod) and starts the recursion by calling dfs(0, 0), which indicates starting from the first index with a seat count of zero.

After exploring all options, the dfs.cache_clear() is called to clear the cache, which is a good practice to release the memory used by the cache when it is no longer needed, and the total number of ways (ans) is returned.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's illustrate the solution approach using a small example corridor string corridor = "SSPPSPS". We aim to find the total number of ways we can divide this corridor into sections so that each section contains exactly two seats.

Here's a step-by-step walkthrough of the solution approach:

We initialize our recursion with dfs(0, 0) which means we start at index 0 with 0 seats counted so far.
We encounter the first seat at index 0. Now our call is dfs(1, 1) since we've found 1 seat.
The next character at index 1 is also a seat. We're now calling dfs(2, 2) and have a branching point. We can:
- Place a divider (dfs(3, 0)) because we completed a section with exactly two seats.
- Not place a divider and just continue to the next character.
Assuming we place a divider, our new state is dfs(3, 0). At index 3, we find a plant and the call becomes dfs(4, 0).
We reach another 'S' at index 4, making our state dfs(5, 1).
At index 5, we find a plant, and again, continue to dfs(6, 1).
At index 6, we reach the last seat, and our state is dfs(7, 2). Since we have two seats, we have two options:
- End the recursion (returning 1) because we are at the end (i == n) and we have a valid section.
- Call dfs(7, 0) to start looking beyond the last index for more seats, which is not possible since we're at the end.
We can now backtrack to previous choices where we didn't place a divider and look at potential divisions there, applying the same decision process.
Throughout the exploration, the @cache decorator ensures we don't recompute states we've already processed.
Once all possible paths are walked through, the total number of ways is summed up, taking into account the modulo 10^9 + 7 to keep the numbers within bounds.

For each index we are considering, we have two main choices leading to two recursive calls: advance with the same count of seats or reset the seat count if we placed a divider. This process will explore all valid combinations of placing dividers.

In this specific example, we have two places where we can potentially place additional dividers (after the first and the last seat). So the example corridor = "SSPPSPS" can be divided in the following ways:

"SS" | "PPSPS"
"SSPPSPS"

Therefore, there are 2 ways to divide the corridor into sections with exactly two seats each.

Solution Implementation

1from functools import lru_cache  # Importing cache mechanism for memoization
2
3class Solution:
4    def numberOfWays(self, corridor: str) -> int:
5        # This function uses depth-first search to count the number of ways 
6        # to partition the corridor keeping the constraints in mind.
7        @lru_cache(None)  # Using least recently used cache for memoization
8        def dfs(index, seat_count):
9            # If we've reached the end of the corridor, return 1 if we have exactly 2 seats,
10            # otherwise return 0 since the current pathway is invalid.
11            if index == corridor_length:
12                return int(seat_count == 2)
13          
14            # Increment seat_count if the current position has a seat 'S'
15            seat_count += corridor[index] == 'S'
16          
17            # If the count exceeds 2, we cannot make any more partitions, thus return 0
18            if seat_count > 2:
19                return 0
20          
21            # Continue searching along the corridor with the current seat count
22            ways = dfs(index + 1, seat_count)
23          
24            # If we have exactly 2 seats so far, we have an option to partition here
25            if seat_count == 2:
26                ways += dfs(index + 1, 0)  # Reset seat_count after partitioning
27                ways %= mod  # Take mod to prevent overflow
28          
29            return ways
30
31        corridor_length = len(corridor)  # Store the length of the corridor
32        mod = 10**9 + 7  # Modulus to avoid integer overflow issues
33        result = dfs(0, 0)  # Start the DFS from index 0 with seat count 0
34        dfs.cache_clear()  # Clear the cache after computation
35        return result  # Return the total number of ways to partition the corridor
36
37# This code can now be used as follows:
38# sol = Solution()
39# print(sol.numberOfWays("SSPPSPS"))
40

1import java.util.Arrays; // Import Arrays to use Arrays.fill()
2
3class Solution {
4    // Variables used across methods
5    private String corridor;
6    private int corridorLength;
7    private int[][] memoization;
8    private static final int MODULO = (int) 1e9 + 7; // Using a more descriptive constant name
9
10    public int numberOfWays(String corridor) {
11        this.corridor = corridor;
12        corridorLength = corridor.length();
13        memoization = new int[corridorLength][3]; // Store the computed values for dynamic programming
14
15        // Initialize memoization array with -1, which signifies that the value has not been computed
16        for (var element : memoization) {
17            Arrays.fill(element, -1);
18        }
19      
20        // Start the search from position 0 with 0 'S' plants encountered
21        return depthFirstSearch(0, 0);
22    }
23
24    // Helper method for depth-first search
25    // 'index' represents the current index in the corridor string
26    // 'seatCount' counts the number of 'S' plants encountered
27    private int depthFirstSearch(int index, int seatCount) {
28        // If we reach the end of the string
29        if (index == corridorLength) {
30            // Check if we have exactly 2 'S' plants, which is required to form a valid section
31            return seatCount == 2 ? 1 : 0;
32        }
33      
34        // If adding a seat exceeds the allowed number for a valid section, return 0
35        seatCount += corridor.charAt(index) == 'S' ? 1 : 0;
36        if (seatCount > 2) {
37            return 0;
38        }
39      
40        // Check for memoized results to avoid recomputation
41        if (memoization[index][seatCount] != -1) {
42            return memoization[index][seatCount];
43        }
44      
45        // Continue to the next seat
46        int possibleWays = depthFirstSearch(index + 1, seatCount);
47      
48        // If there are 2 'S' plants, we have an option to start a new section
49        if (seatCount == 2) {
50            possibleWays += depthFirstSearch(index + 1, 0);
51            // Ensure the result is within the modulo range
52            possibleWays %= MODULO;
53        }
54      
55        // Memoize the calculated ways for current state
56        memoization[index][seatCount] = possibleWays;
57        return possibleWays;
58    }
59}
60

1class Solution {
2public:
3    const int MOD = 1e9 + 7; // Constant for the modulus operation
4
5    // Function to compute the number of ways to sit people in the corridor
6    int numberOfWays(string corridor) {
7        int corridorLength = corridor.size(); // Get the length of the corridor
8        vector<vector<int>> dp(corridorLength, vector<int>(3, -1)); // Dynamic programming table initialized with -1, representing uncomputed states
9
10        // Declare the depth-first search function to find the number of ways
11        // cnt represents the current number of people sitting consecutively. It must not exceed 2.
12        function<int(int, int)> dfs = [&](int index, int count) {
13            // If we reach the end of the string, return 1 if count is 2, else 0
14            if (index == corridorLength) return count == 2 ? 1 : 0;
15          
16            // Increment the count if we find a seat (represented by 'S')
17            count += corridor[index] == 'S';
18          
19            // If count exceeds 2, return 0 as it's an invalid placement
20            if (count > 2) return 0;
21          
22            // Return the precomputed value if it's already calculated
23            if (dp[index][count] != -1) return dp[index][count];
24          
25            // Recursive case: continue to the next index with the current count
26            int ways = dfs(index + 1, count);
27          
28            // If we have exactly 2 people sitting, we can reset the count and add the ways from this point
29            if (count == 2) {
30                ways += dfs(index + 1, 0);
31                ways %= MOD; // Ensure the result stays within the bounds of the modulus
32            }
33          
34            // Save the computed value in the dynamic programming table before returning
35            dp[index][count] = ways;
36            return ways;
37        };
38      
39        return dfs(0, 0); // Start the DFS from index 0 with 0 people sitting consecutively
40    }
41};
42

1// Constant for the modulus operation
2const MOD: number = 1e9 + 7;
3
4// Function to compute the number of ways to sit people in the corridor
5function numberOfWays(corridor: string): number {
6    let corridorLength: number = corridor.length; // Get the length of the corridor
7    let dp: number[][] = Array.from({ length: corridorLength }, () => Array(3).fill(-1)); // Dynamic programming table initialized with -1, representing uncomputed states
8
9    // The depth-first search function finds the number of ways
10    // `count` represents the current number of people sitting consecutively. It must not exceed 2.
11    const dfs = (index: number, count: number): number => {
12        // If we reach the end of the string, return 1 if count is 2, else 0
13        if (index === corridorLength) return count === 2 ? 1 : 0;
14
15        // Increment the count if we find a seat (represented by 'S')
16        count += corridor[index] === 'S' ? 1 : 0;
17
18        // If count exceeds 2, return 0 as it's an invalid placement
19        if (count > 2) return 0;
20
21        // Return the precomputed value if it's already calculated
22        if (dp[index][count] !== -1) return dp[index][count];
23
24        // Recursive case: continue to the next index with the current count
25        let ways = dfs(index + 1, count);
26
27        // If we have exactly 2 people sitting, we can reset the count and add the ways from this point
28        if (count === 2) {
29            ways += dfs(index + 1, 0);
30            ways %= MOD; // Ensure the result stays within the bounds of the modulus
31        }
32
33        // Save the computed value in the dynamic programming table before returning
34        dp[index][count] = ways;
35        return ways;
36    };
37
38    return dfs(0, 0); // Start the DFS from index 0 with 0 people sitting consecutively
39}
40

Time and Space Complexity

Time Complexity

The time complexity of the given code mainly comes from the recursive function dfs. The function has two parameters: the index i and the count of 'S' seen so far cnt. The recursion has three cases:

Base case when i == n, which takes O(1) time.
The recursive case without changing cnt, which in the worst case, can be called for each character in the corridor string—resulting in O(n).
The recursive case where cnt == 2 can double the number of calls, as it leads to another call with cnt reset to 0.

With memoization, we prevent recalculating the results for the same state (i, cnt). There are n different values for i and 3 values for cnt (0, 1, and 2), giving us at most O(n) states.

Each state requires constant time to process, except for the recursive calls. Since memoization ensures we compute each state at most once, and the recursion fan-out is capped (only two recursive calls per invocation), the overall time complexity is O(n).

Space Complexity

The space complexity includes the space for the recursive stack and the memoization cache.

Recursive stack: In the worst case, there could be O(n) calls in the call stack since dfs gets called with each increasing index i up to n.
Memoization cache: We store a result for each possible state (i, cnt). As established, there are n positions for i, and cnt can have 3 values leading to O(n) space complexity for the cache.

Therefore, the overall space complexity of the code is also O(n), with the primary contributions being the recursion stack and the memoization cache.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know