2147. Number of Ways to Divide a Long Corridor - Explanation

Description

The string corridor describes a row of seats (S) and plants (P). Its two ends are already closed by dividers. You may add at most one divider in any gap between adjacent characters. Count the ways to partition the entire row so that every section contains exactly two seats and any number of plants. Different sets of divider positions count as different ways. Return the count modulo 1000000007, or 0 if no valid partition exists.

Dashed lines mark possible divider positions between groups of two seats; choose one divider in each such gap.

Example 1:

Number of Ways to Divide a Long Corridor, example 1: illustration of the example

Input: corridor = "SSPSS"

Output: 2

Explanation: The two valid partitions are SS | PSS and SSP | SS. Each section has exactly two seats.

Example 2:

Number of Ways to Divide a Long Corridor, example 2: illustration of the example

Input: corridor = "PSSP"

Output: 1

Explanation: There are exactly two seats in the entire corridor, so the only valid choice is to add no divider.

Example 3:

Number of Ways to Divide a Long Corridor, example 3: illustration of the example

Input: corridor = "SSS"

Output: 0

Explanation: There are three seats. Sections of exactly two seats cannot cover an odd number of seats, so no partition is valid.

Constraints:

1 <= corridor.length <= 100000
Every character is S or P.

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Dynamic Programming - Used to count valid ways by tracking seat counts in each section
Memoization - Caching subproblem results to avoid redundant computation
Modular Arithmetic - Required for handling large results modulo 10^9+7
Combinatorics - The optimal approach counts divider positions between seat pairs using multiplication

1. Dynamic Programming (Top-Down)

Intuition

We need to divide the corridor so each section has exactly two seats. The key insight is that after placing two seats in a section, we have a choice: place the divider immediately after the second seat, or delay it through any number of plants. Each plant between the second seat of one section and the first seat of the next section represents a possible divider position.

Algorithm

Define a recursive function dfs(i, seats) where i is the current index and seats counts how many seats are in the current section (0, 1, or 2).
Base case: If we reach the end of the corridor, return 1 if we have exactly 2 seats (valid section), otherwise 0.
If we already have 2 seats in the current section:
- If the current position is a seat, we must start a new section (reset seats to 1).
- If it's a plant, we can either place the divider here (reset to 0) or continue without dividing (keep at 2).
If we have fewer than 2 seats, count the seat if present and continue.
Use memoization to cache results.

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        mod = 10**9 + 7
        cache = [[-1] * 3 for i in range(len(corridor))]  # (i, seats) -> count

        def dfs(i, seats):
            if i == len(corridor):
                return 1 if seats == 2 else 0
            if cache[i][seats] != -1:
                return cache[i][seats]

            res = 0
            if seats == 2:
                if corridor[i] == "S":
                    res = dfs(i + 1, 1)
                else:
                    res = (dfs(i + 1, 0) + dfs(i + 1, 2)) % mod
            else:
                if corridor[i] == "S":
                    res = dfs(i + 1, seats + 1)
                else:
                    res = dfs(i + 1, seats)

            cache[i][seats] = res
            return res

        return dfs(0, 0)

public class Solution {
    private static final int MOD = 1_000_000_007;
    private int[][] dp;

    public int numberOfWays(String corridor) {
        int n = corridor.length();
        dp = new int[n][3];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        return dfs(0, 0, corridor);
    }

    private int dfs(int i, int seats, String corridor) {
        if (i == corridor.length()) {
            return seats == 2 ? 1 : 0;
        }
        if (dp[i][seats] != -1) {
            return dp[i][seats];
        }

        int res = 0;
        if (seats == 2) {
            if (corridor.charAt(i) == 'S') {
                res = dfs(i + 1, 1, corridor);
            } else {
                res = (dfs(i + 1, 0, corridor) + dfs(i + 1, 2, corridor)) % MOD;
            }
        } else {
            if (corridor.charAt(i) == 'S') {
                res = dfs(i + 1, seats + 1, corridor);
            } else {
                res = dfs(i + 1, seats, corridor);
            }
        }

        return dp[i][seats] = res;
    }
}

class Solution {
public:
    static constexpr int MOD = 1'000'000'007;
    vector<vector<int>> dp;

    int numberOfWays(string corridor) {
        int n = corridor.size();
        dp.assign(n, vector<int>(3, -1));
        return dfs(0, 0, corridor);
    }

    int dfs(int i, int seats, string& corridor) {
        if (i == corridor.size()) {
            return seats == 2 ? 1 : 0;
        }
        if (dp[i][seats] != -1) {
            return dp[i][seats];
        }

        int res = 0;
        if (seats == 2) {
            if (corridor[i] == 'S') {
                res = dfs(i + 1, 1, corridor);
            } else {
                res = (dfs(i + 1, 0, corridor) + dfs(i + 1, 2, corridor)) % MOD;
            }
        } else {
            if (corridor[i] == 'S') {
                res = dfs(i + 1, seats + 1, corridor);
            } else {
                res = dfs(i + 1, seats, corridor);
            }
        }

        return dp[i][seats] = res;
    }
};

class Solution {
    /**
     * @param {string} corridor
     * @return {number}
     */
    numberOfWays(corridor) {
        const MOD = 1_000_000_007;
        const n = corridor.length;
        const dp = Array.from({ length: n }, () => Array(3).fill(-1));

        const dfs = (i, seats) => {
            if (i === n) return seats === 2 ? 1 : 0;
            if (dp[i][seats] !== -1) return dp[i][seats];

            let res = 0;
            if (seats === 2) {
                if (corridor[i] === 'S') {
                    res = dfs(i + 1, 1);
                } else {
                    res = (dfs(i + 1, 0) + dfs(i + 1, 2)) % MOD;
                }
            } else {
                if (corridor[i] === 'S') {
                    res = dfs(i + 1, seats + 1);
                } else {
                    res = dfs(i + 1, seats);
                }
            }

            return (dp[i][seats] = res);
        };

        return dfs(0, 0);
    }
}

public class Solution {
    private const int MOD = 1_000_000_007;
    private int[,] dp;

    public int NumberOfWays(string corridor) {
        int n = corridor.Length;
        dp = new int[n, 3];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 3; j++) {
                dp[i, j] = -1;
            }
        }
        return Dfs(0, 0, corridor);
    }

    private int Dfs(int i, int seats, string corridor) {
        if (i == corridor.Length) {
            return seats == 2 ? 1 : 0;
        }
        if (dp[i, seats] != -1) {
            return dp[i, seats];
        }

        int res = 0;
        if (seats == 2) {
            if (corridor[i] == 'S') {
                res = Dfs(i + 1, 1, corridor);
            } else {
                res = (Dfs(i + 1, 0, corridor) + Dfs(i + 1, 2, corridor)) % MOD;
            }
        } else {
            if (corridor[i] == 'S') {
                res = Dfs(i + 1, seats + 1, corridor);
            } else {
                res = Dfs(i + 1, seats, corridor);
            }
        }

        return dp[i, seats] = res;
    }
}

func numberOfWays(corridor string) int {
    MOD := 1_000_000_007
    n := len(corridor)
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = []int{-1, -1, -1}
    }

    var dfs func(i, seats int) int
    dfs = func(i, seats int) int {
        if i == n {
            if seats == 2 {
                return 1
            }
            return 0
        }
        if dp[i][seats] != -1 {
            return dp[i][seats]
        }

        res := 0
        if seats == 2 {
            if corridor[i] == 'S' {
                res = dfs(i+1, 1)
            } else {
                res = (dfs(i+1, 0) + dfs(i+1, 2)) % MOD
            }
        } else {
            if corridor[i] == 'S' {
                res = dfs(i+1, seats+1)
            } else {
                res = dfs(i+1, seats)
            }
        }

        dp[i][seats] = res
        return res
    }

    return dfs(0, 0)
}

class Solution {
    private val MOD = 1_000_000_007
    private lateinit var dp: Array<IntArray>

    fun numberOfWays(corridor: String): Int {
        val n = corridor.length
        dp = Array(n) { IntArray(3) { -1 } }
        return dfs(0, 0, corridor)
    }

    private fun dfs(i: Int, seats: Int, corridor: String): Int {
        if (i == corridor.length) {
            return if (seats == 2) 1 else 0
        }
        if (dp[i][seats] != -1) {
            return dp[i][seats]
        }

        val res: Int
        if (seats == 2) {
            res = if (corridor[i] == 'S') {
                dfs(i + 1, 1, corridor)
            } else {
                (dfs(i + 1, 0, corridor) + dfs(i + 1, 2, corridor)) % MOD
            }
        } else {
            res = if (corridor[i] == 'S') {
                dfs(i + 1, seats + 1, corridor)
            } else {
                dfs(i + 1, seats, corridor)
            }
        }

        dp[i][seats] = res
        return res
    }
}

class Solution {
    func numberOfWays(_ corridor: String) -> Int {
        let MOD = 1_000_000_007
        let n = corridor.count
        let chars = Array(corridor)
        var dp = [[Int]](repeating: [-1, -1, -1], count: n)

        func dfs(_ i: Int, _ seats: Int) -> Int {
            if i == n {
                return seats == 2 ? 1 : 0
            }
            if dp[i][seats] != -1 {
                return dp[i][seats]
            }

            var res = 0
            if seats == 2 {
                if chars[i] == "S" {
                    res = dfs(i + 1, 1)
                } else {
                    res = (dfs(i + 1, 0) + dfs(i + 1, 2)) % MOD
                }
            } else {
                if chars[i] == "S" {
                    res = dfs(i + 1, seats + 1)
                } else {
                    res = dfs(i + 1, seats)
                }
            }

            dp[i][seats] = res
            return res
        }

        return dfs(0, 0)
    }
}

impl Solution {
    pub fn number_of_ways(corridor: String) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let chars: Vec<u8> = corridor.into_bytes();
        let n = chars.len();
        let mut dp = vec![[-1i32; 3]; n];

        fn dfs(chars: &[u8], dp: &mut Vec<[i32; 3]>, i: usize, seats: usize) -> i32 {
            if i == chars.len() {
                return if seats == 2 { 1 } else { 0 };
            }
            if dp[i][seats] != -1 {
                return dp[i][seats];
            }
            let res = if seats == 2 {
                if chars[i] == b'S' {
                    dfs(chars, dp, i + 1, 1)
                } else {
                    (dfs(chars, dp, i + 1, 0) + dfs(chars, dp, i + 1, 2)) % MOD
                }
            } else {
                if chars[i] == b'S' {
                    dfs(chars, dp, i + 1, seats + 1)
                } else {
                    dfs(chars, dp, i + 1, seats)
                }
            };
            dp[i][seats] = res;
            res
        }

        dfs(&chars, &mut dp, 0, 0)
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Dynamic Programming (Bottom-Up)

Intuition

We can convert the top-down approach to bottom-up by iterating from the end of the corridor to the beginning. For each position, we compute the number of ways based on whether we have 0, 1, or 2 seats in the current section.

Algorithm

Create a DP table where dp[i][seats] represents the number of ways to divide from index i onward with seats seats in the current section.
Initialize dp[n][2] = 1 (reaching the end with exactly 2 seats is one valid way).
Iterate backward through the corridor:
- For each position and seat count, apply the same transitions as the top-down approach.
Return dp[0][0] (starting from index 0 with 0 seats).

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        MOD = 1000000007
        n = len(corridor)
        dp = [[0] * 3 for _ in range(n + 1)]
        dp[n][2] = 1

        for i in range(n - 1, -1, -1):
            for seats in range(3):
                if seats == 2:
                    if corridor[i] == 'S':
                        dp[i][seats] = dp[i + 1][1]
                    else:
                        dp[i][seats] = (dp[i + 1][0] + dp[i + 1][2]) % MOD
                else:
                    if corridor[i] == 'S':
                        dp[i][seats] = dp[i + 1][seats + 1]
                    else:
                        dp[i][seats] = dp[i + 1][seats]

        return dp[0][0]

public class Solution {
    public int numberOfWays(String corridor) {
        int MOD = 1000000007;
        int n = corridor.length();
        int[][] dp = new int[n + 1][3];
        dp[n][2] = 1;

        for (int i = n - 1; i >= 0; i--) {
            for (int seats = 0; seats < 3; seats++) {
                if (seats == 2) {
                    if (corridor.charAt(i) == 'S') {
                        dp[i][seats] = dp[i + 1][1];
                    } else {
                        dp[i][seats] = (dp[i + 1][0] + dp[i + 1][2]) % MOD;
                    }
                } else {
                    if (corridor.charAt(i) == 'S') {
                        dp[i][seats] = dp[i + 1][seats + 1];
                    } else {
                        dp[i][seats] = dp[i + 1][seats];
                    }
                }
            }
        }
        return dp[0][0];
    }
}

class Solution {
public:
    int numberOfWays(string corridor) {
        int MOD = 1000000007;
        int n = corridor.size();
        vector<vector<int>> dp(n + 1, vector<int>(3, 0));
        dp[n][2] = 1;

        for (int i = n - 1; i >= 0; i--) {
            for (int seats = 0; seats < 3; seats++) {
                if (seats == 2) {
                    if (corridor[i] == 'S') {
                        dp[i][seats] = dp[i + 1][1];
                    } else {
                        dp[i][seats] = (dp[i + 1][0] + dp[i + 1][2]) % MOD;
                    }
                } else {
                    if (corridor[i] == 'S') {
                        dp[i][seats] = dp[i + 1][seats + 1];
                    } else {
                        dp[i][seats] = dp[i + 1][seats];
                    }
                }
            }
        }
        return dp[0][0];
    }
};

class Solution {
    /**
     * @param {string} corridor
     * @return {number}
     */
    numberOfWays(corridor) {
        const MOD = 1000000007;
        const n = corridor.length;
        let dp = Array.from({ length: n + 1 }, () => Array(3).fill(0));
        dp[n][2] = 1;

        for (let i = n - 1; i >= 0; i--) {
            for (let seats = 0; seats < 3; seats++) {
                if (seats === 2) {
                    if (corridor[i] === 'S') {
                        dp[i][seats] = dp[i + 1][1];
                    } else {
                        dp[i][seats] = (dp[i + 1][0] + dp[i + 1][2]) % MOD;
                    }
                } else {
                    if (corridor[i] === 'S') {
                        dp[i][seats] = dp[i + 1][seats + 1];
                    } else {
                        dp[i][seats] = dp[i + 1][seats];
                    }
                }
            }
        }
        return dp[0][0];
    }
}

public class Solution {
    public int NumberOfWays(string corridor) {
        int MOD = 1000000007;
        int n = corridor.Length;
        int[,] dp = new int[n + 1, 3];
        dp[n, 2] = 1;

        for (int i = n - 1; i >= 0; i--) {
            for (int seats = 0; seats < 3; seats++) {
                if (seats == 2) {
                    if (corridor[i] == 'S') {
                        dp[i, seats] = dp[i + 1, 1];
                    } else {
                        dp[i, seats] = (dp[i + 1, 0] + dp[i + 1, 2]) % MOD;
                    }
                } else {
                    if (corridor[i] == 'S') {
                        dp[i, seats] = dp[i + 1, seats + 1];
                    } else {
                        dp[i, seats] = dp[i + 1, seats];
                    }
                }
            }
        }
        return dp[0, 0];
    }
}

func numberOfWays(corridor string) int {
    MOD := 1000000007
    n := len(corridor)
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, 3)
    }
    dp[n][2] = 1

    for i := n - 1; i >= 0; i-- {
        for seats := 0; seats < 3; seats++ {
            if seats == 2 {
                if corridor[i] == 'S' {
                    dp[i][seats] = dp[i+1][1]
                } else {
                    dp[i][seats] = (dp[i+1][0] + dp[i+1][2]) % MOD
                }
            } else {
                if corridor[i] == 'S' {
                    dp[i][seats] = dp[i+1][seats+1]
                } else {
                    dp[i][seats] = dp[i+1][seats]
                }
            }
        }
    }
    return dp[0][0]
}

class Solution {
    fun numberOfWays(corridor: String): Int {
        val MOD = 1000000007
        val n = corridor.length
        val dp = Array(n + 1) { IntArray(3) }
        dp[n][2] = 1

        for (i in n - 1 downTo 0) {
            for (seats in 0 until 3) {
                if (seats == 2) {
                    if (corridor[i] == 'S') {
                        dp[i][seats] = dp[i + 1][1]
                    } else {
                        dp[i][seats] = (dp[i + 1][0] + dp[i + 1][2]) % MOD
                    }
                } else {
                    if (corridor[i] == 'S') {
                        dp[i][seats] = dp[i + 1][seats + 1]
                    } else {
                        dp[i][seats] = dp[i + 1][seats]
                    }
                }
            }
        }
        return dp[0][0]
    }
}

class Solution {
    func numberOfWays(_ corridor: String) -> Int {
        let MOD = 1000000007
        let n = corridor.count
        let chars = Array(corridor)
        var dp = [[Int]](repeating: [0, 0, 0], count: n + 1)
        dp[n][2] = 1

        for i in stride(from: n - 1, through: 0, by: -1) {
            for seats in 0..<3 {
                if seats == 2 {
                    if chars[i] == "S" {
                        dp[i][seats] = dp[i + 1][1]
                    } else {
                        dp[i][seats] = (dp[i + 1][0] + dp[i + 1][2]) % MOD
                    }
                } else {
                    if chars[i] == "S" {
                        dp[i][seats] = dp[i + 1][seats + 1]
                    } else {
                        dp[i][seats] = dp[i + 1][seats]
                    }
                }
            }
        }
        return dp[0][0]
    }
}

impl Solution {
    pub fn number_of_ways(corridor: String) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let chars: Vec<u8> = corridor.into_bytes();
        let n = chars.len();
        let mut dp = vec![[0i32; 3]; n + 1];
        dp[n][2] = 1;

        for i in (0..n).rev() {
            for seats in 0..3 {
                if seats == 2 {
                    if chars[i] == b'S' {
                        dp[i][seats] = dp[i + 1][1];
                    } else {
                        dp[i][seats] = (dp[i + 1][0] + dp[i + 1][2]) % MOD;
                    }
                } else {
                    if chars[i] == b'S' {
                        dp[i][seats] = dp[i + 1][seats + 1];
                    } else {
                        dp[i][seats] = dp[i + 1][seats];
                    }
                }
            }
        }
        dp[0][0]
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Dynamic Programming (Space Optimized)

Intuition

Since each row of the DP table only depends on the next row, we can reduce space by maintaining just a single array of size 3 (for the three possible seat counts).

Algorithm

Initialize a DP array of size 3 with dp[2] = 1.
Iterate backward through the corridor:
- Create a new DP array and compute transitions based on whether the current position is a seat or plant.
- Replace the old DP array with the new one.
Return dp[0].

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        MOD = 1000000007
        dp = [0, 0, 1]

        for i in reversed(corridor):
            new_dp = [0] * 3
            for seats in range(3):
                if seats == 2:
                    new_dp[seats] = dp[1] if i == 'S' else (dp[0] + dp[2]) % MOD
                else:
                    new_dp[seats] = dp[seats + 1] if i == 'S' else dp[seats]
            dp = new_dp

        return dp[0]

public class Solution {
    public int numberOfWays(String corridor) {
        int MOD = 1000000007;
        int[] dp = {0, 0, 1};

        for (int i = corridor.length() - 1; i >= 0; i--) {
            int[] new_dp = new int[3];
            for (int seats = 0; seats < 3; seats++) {
                if (seats == 2) {
                    new_dp[seats] = corridor.charAt(i) == 'S' ? dp[1] : (dp[0] + dp[2]) % MOD;
                } else {
                    new_dp[seats] = corridor.charAt(i) == 'S' ? dp[seats + 1] : dp[seats];
                }
            }
            dp = new_dp;
        }
        return dp[0];
    }
}

class Solution {
public:
    int numberOfWays(string corridor) {
        const int MOD = 1000000007;
        vector<int> dp = {0, 0, 1};

        for (int i = corridor.length() - 1; i >= 0; i--) {
            vector<int> new_dp(3, 0);
            for (int seats = 0; seats < 3; seats++) {
                if (seats == 2) {
                    new_dp[seats] = (corridor[i] == 'S') ? dp[1] : (dp[0] + dp[2]) % MOD;
                } else {
                    new_dp[seats] = (corridor[i] == 'S') ? dp[seats + 1] : dp[seats];
                }
            }
            dp = new_dp;
        }
        return dp[0];
    }
};

class Solution {
    /**
     * @param {string} corridor
     * @return {number}
     */
    numberOfWays(corridor) {
        const MOD = 1000000007;
        let dp = [0, 0, 1];

        for (let i = corridor.length - 1; i >= 0; i--) {
            let new_dp = [0, 0, 0];
            for (let seats = 0; seats < 3; seats++) {
                if (seats === 2) {
                    new_dp[seats] =
                        corridor[i] === 'S' ? dp[1] : (dp[0] + dp[2]) % MOD;
                } else {
                    new_dp[seats] =
                        corridor[i] === 'S' ? dp[seats + 1] : dp[seats];
                }
            }
            dp = new_dp;
        }
        return dp[0];
    }
}

public class Solution {
    public int NumberOfWays(string corridor) {
        int MOD = 1000000007;
        int[] dp = { 0, 0, 1 };

        for (int i = corridor.Length - 1; i >= 0; i--) {
            int[] new_dp = new int[3];
            for (int seats = 0; seats < 3; seats++) {
                if (seats == 2) {
                    new_dp[seats] = corridor[i] == 'S' ? dp[1] : (dp[0] + dp[2]) % MOD;
                } else {
                    new_dp[seats] = corridor[i] == 'S' ? dp[seats + 1] : dp[seats];
                }
            }
            dp = new_dp;
        }
        return dp[0];
    }
}

func numberOfWays(corridor string) int {
    MOD := 1000000007
    dp := []int{0, 0, 1}

    for i := len(corridor) - 1; i >= 0; i-- {
        newDp := make([]int, 3)
        for seats := 0; seats < 3; seats++ {
            if seats == 2 {
                if corridor[i] == 'S' {
                    newDp[seats] = dp[1]
                } else {
                    newDp[seats] = (dp[0] + dp[2]) % MOD
                }
            } else {
                if corridor[i] == 'S' {
                    newDp[seats] = dp[seats+1]
                } else {
                    newDp[seats] = dp[seats]
                }
            }
        }
        dp = newDp
    }
    return dp[0]
}

class Solution {
    fun numberOfWays(corridor: String): Int {
        val MOD = 1000000007
        var dp = intArrayOf(0, 0, 1)

        for (i in corridor.length - 1 downTo 0) {
            val newDp = IntArray(3)
            for (seats in 0 until 3) {
                if (seats == 2) {
                    newDp[seats] = if (corridor[i] == 'S') dp[1] else (dp[0] + dp[2]) % MOD
                } else {
                    newDp[seats] = if (corridor[i] == 'S') dp[seats + 1] else dp[seats]
                }
            }
            dp = newDp
        }
        return dp[0]
    }
}

class Solution {
    func numberOfWays(_ corridor: String) -> Int {
        let MOD = 1000000007
        let chars = Array(corridor)
        var dp = [0, 0, 1]

        for i in stride(from: chars.count - 1, through: 0, by: -1) {
            var newDp = [0, 0, 0]
            for seats in 0..<3 {
                if seats == 2 {
                    newDp[seats] = chars[i] == "S" ? dp[1] : (dp[0] + dp[2]) % MOD
                } else {
                    newDp[seats] = chars[i] == "S" ? dp[seats + 1] : dp[seats]
                }
            }
            dp = newDp
        }
        return dp[0]
    }
}

impl Solution {
    pub fn number_of_ways(corridor: String) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let chars: Vec<u8> = corridor.into_bytes();
        let mut dp = [0i32, 0, 1];

        for i in (0..chars.len()).rev() {
            let mut new_dp = [0i32; 3];
            for seats in 0..3 {
                if seats == 2 {
                    new_dp[seats] = if chars[i] == b'S' { dp[1] } else { (dp[0] + dp[2]) % MOD };
                } else {
                    new_dp[seats] = if chars[i] == b'S' { dp[seats + 1] } else { dp[seats] };
                }
            }
            dp = new_dp;
        }
        dp[0]
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

4. Combinatorics

Intuition

Instead of DP, we can think combinatorially. First, collect all seat positions. If the count isn't even or is less than 2, there's no valid way. Otherwise, between every pair of seats (the 2nd and 3rd, 4th and 5th, etc.), we can place the divider at any position including those occupied by plants. The number of choices at each gap is the distance between consecutive pairs of seats.

Algorithm

Collect the indices of all seats in a list.
If the seat count is less than 2 or odd, return 0.
For every pair of adjacent seat groups (positions 1 and 2, positions 3 and 4, etc.), multiply res by the gap size seats[i+1] - seats[i].
Return res modulo 10^9 + 7.

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        mod = 10**9 + 7
        seats = [i for i, c in enumerate(corridor) if c == "S"]

        length = len(seats)
        if length < 2 or length % 2 == 1:
            return 0

        res = 1
        for i in range(1, length - 1, 2):
            res = (res * (seats[i + 1] - seats[i])) % mod

        return res

public class Solution {
    public int numberOfWays(String corridor) {
        int mod = 1_000_000_007;
        List<Integer> seats = new ArrayList<>();

        for (int i = 0; i < corridor.length(); i++) {
            if (corridor.charAt(i) == 'S') {
                seats.add(i);
            }
        }

        int length = seats.size();
        if (length < 2 || length % 2 == 1) {
            return 0;
        }

        long res = 1;
        for (int i = 1; i < length - 1; i += 2) {
            res = (res * (seats.get(i + 1) - seats.get(i))) % mod;
        }

        return (int) res;
    }
}

class Solution {
public:
    int numberOfWays(string corridor) {
        int mod = 1'000'000'007;
        vector<int> seats;

        for (int i = 0; i < corridor.size(); i++) {
            if (corridor[i] == 'S') {
                seats.push_back(i);
            }
        }

        int length = seats.size();
        if (length < 2 || length % 2 == 1) {
            return 0;
        }

        long long res = 1;
        for (int i = 1; i < length - 1; i += 2) {
            res = (res * (seats[i + 1] - seats[i])) % mod;
        }

        return res;
    }
};

class Solution {
    /**
     * @param {string} corridor
     * @return {number}
     */
    numberOfWays(corridor) {
        const mod = 1_000_000_007;
        const seats = [];

        for (let i = 0; i < corridor.length; i++) {
            if (corridor[i] === 'S') {
                seats.push(i);
            }
        }

        const length = seats.length;
        if (length < 2 || length % 2 === 1) {
            return 0;
        }

        let res = 1;
        for (let i = 1; i < length - 1; i += 2) {
            res = (res * (seats[i + 1] - seats[i])) % mod;
        }

        return res;
    }
}

public class Solution {
    public int NumberOfWays(string corridor) {
        int mod = 1_000_000_007;
        var seats = new List<int>();

        for (int i = 0; i < corridor.Length; i++) {
            if (corridor[i] == 'S') {
                seats.Add(i);
            }
        }

        int length = seats.Count;
        if (length < 2 || length % 2 == 1) {
            return 0;
        }

        long res = 1;
        for (int i = 1; i < length - 1; i += 2) {
            res = (res * (seats[i + 1] - seats[i])) % mod;
        }

        return (int)res;
    }
}

func numberOfWays(corridor string) int {
    mod := 1_000_000_007
    seats := []int{}

    for i := 0; i < len(corridor); i++ {
        if corridor[i] == 'S' {
            seats = append(seats, i)
        }
    }

    length := len(seats)
    if length < 2 || length%2 == 1 {
        return 0
    }

    res := 1
    for i := 1; i < length-1; i += 2 {
        res = (res * (seats[i+1] - seats[i])) % mod
    }

    return res
}

class Solution {
    fun numberOfWays(corridor: String): Int {
        val mod = 1_000_000_007
        val seats = mutableListOf<Int>()

        for (i in corridor.indices) {
            if (corridor[i] == 'S') {
                seats.add(i)
            }
        }

        val length = seats.size
        if (length < 2 || length % 2 == 1) {
            return 0
        }

        var res = 1L
        for (i in 1 until length - 1 step 2) {
            res = (res * (seats[i + 1] - seats[i])) % mod
        }

        return res.toInt()
    }
}

class Solution {
    func numberOfWays(_ corridor: String) -> Int {
        let mod = 1_000_000_007
        var seats = [Int]()
        let chars = Array(corridor)

        for i in 0..<chars.count {
            if chars[i] == "S" {
                seats.append(i)
            }
        }

        let length = seats.count
        if length < 2 || length % 2 == 1 {
            return 0
        }

        var res = 1
        for i in stride(from: 1, to: length - 1, by: 2) {
            res = (res * (seats[i + 1] - seats[i])) % mod
        }

        return res
    }
}

impl Solution {
    pub fn number_of_ways(corridor: String) -> i32 {
        let modulo: i64 = 1_000_000_007;
        let seats: Vec<usize> = corridor
            .bytes()
            .enumerate()
            .filter(|&(_, c)| c == b'S')
            .map(|(i, _)| i)
            .collect();

        let length = seats.len();
        if length < 2 || length % 2 == 1 {
            return 0;
        }

        let mut res: i64 = 1;
        for i in (1..length - 1).step_by(2) {
            res = (res * (seats[i + 1] - seats[i]) as i64) % modulo;
        }

        res as i32
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

5. Combinatorics (Optimal)

Intuition

We can optimize the combinatorics approach by not storing all seat positions. Instead, we track the count of seats and the position of the previous seat. Whenever we complete a pair (seat count becomes even and greater than 2), we multiply by the gap between the current seat and the previous one.

Algorithm

Initialize count = 0, res = 1, and prev = -1 to track the position of the last seat.
Iterate through the corridor:
- When a seat is found, increment count.
- If count > 2 and count % 2 == 1 (meaning we just started a new section), multiply res by the distance from prev.
- Update prev to the current position.
If count >= 2 and count % 2 == 0, return res; otherwise return 0.

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        mod = 1_000_000_007
        count = 0
        res = 1
        prev = -1

        for i, c in enumerate(corridor):
            if c == 'S':
                count += 1
                if count > 2 and count % 2 == 1:
                    res = (res * (i - prev)) % mod
                prev = i

        return res if count >= 2 and count % 2 == 0 else 0

public class Solution {
    public int numberOfWays(String corridor) {
        int mod = 1_000_000_007;
        int count = 0, res = 1, prev = -1;

        for (int i = 0; i < corridor.length(); i++) {
            if (corridor.charAt(i) == 'S') {
                count++;
                if (count > 2 && count % 2 == 1) {
                    res = (int)((res * (long)(i - prev)) % mod);
                }
                prev = i;
            }
        }

        return (count >= 2 && count % 2 == 0) ? res : 0;
    }
}

class Solution {
public:
    int numberOfWays(string corridor) {
        int mod = 1'000'000'007, count = 0, res = 1, prev = -1;

        for (int i = 0; i < corridor.size(); i++) {
            if (corridor[i] == 'S') {
                count++;
                if (count > 2 && count % 2 == 1) {
                    res = (1LL * res * (i - prev)) % mod;
                }
                prev = i;
            }
        }

        return (count >= 2 && count % 2 == 0) ? res : 0;
    }
};

class Solution {
    /**
     * @param {string} corridor
     * @return {number}
     */
    numberOfWays(corridor) {
        const mod = 1_000_000_007;
        let count = 0,
            res = 1,
            prev = -1;

        for (let i = 0; i < corridor.length; i++) {
            if (corridor[i] === 'S') {
                count++;
                if (count > 2 && count % 2 === 1) {
                    res = (res * (i - prev)) % mod;
                }
                prev = i;
            }
        }

        return count >= 2 && count % 2 === 0 ? res : 0;
    }
}

public class Solution {
    public int NumberOfWays(string corridor) {
        int mod = 1_000_000_007;
        int count = 0, prev = -1;
        long res = 1;

        for (int i = 0; i < corridor.Length; i++) {
            if (corridor[i] == 'S') {
                count++;
                if (count > 2 && count % 2 == 1) {
                    res = (res * (i - prev)) % mod;
                }
                prev = i;
            }
        }

        return (count >= 2 && count % 2 == 0) ? (int)res : 0;
    }
}

func numberOfWays(corridor string) int {
    mod := 1_000_000_007
    count, res, prev := 0, 1, -1

    for i := 0; i < len(corridor); i++ {
        if corridor[i] == 'S' {
            count++
            if count > 2 && count%2 == 1 {
                res = (res * (i - prev)) % mod
            }
            prev = i
        }
    }

    if count >= 2 && count%2 == 0 {
        return res
    }
    return 0
}

class Solution {
    fun numberOfWays(corridor: String): Int {
        val mod = 1_000_000_007
        var count = 0
        var res = 1L
        var prev = -1

        for (i in corridor.indices) {
            if (corridor[i] == 'S') {
                count++
                if (count > 2 && count % 2 == 1) {
                    res = (res * (i - prev)) % mod
                }
                prev = i
            }
        }

        return if (count >= 2 && count % 2 == 0) res.toInt() else 0
    }
}

class Solution {
    func numberOfWays(_ corridor: String) -> Int {
        let mod = 1_000_000_007
        var count = 0
        var res = 1
        var prev = -1
        let chars = Array(corridor)

        for i in 0..<chars.count {
            if chars[i] == "S" {
                count += 1
                if count > 2 && count % 2 == 1 {
                    res = (res * (i - prev)) % mod
                }
                prev = i
            }
        }

        return (count >= 2 && count % 2 == 0) ? res : 0
    }
}

impl Solution {
    pub fn number_of_ways(corridor: String) -> i32 {
        let modulo: i64 = 1_000_000_007;
        let mut count = 0;
        let mut res: i64 = 1;
        let mut prev: i64 = -1;

        for (i, c) in corridor.bytes().enumerate() {
            if c == b'S' {
                count += 1;
                if count > 2 && count % 2 == 1 {
                    res = (res * (i as i64 - prev)) % modulo;
                }
                prev = i as i64;
            }
        }

        if count >= 2 && count % 2 == 0 { res as i32 } else { 0 }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Not Handling Edge Cases for Seat Count

If the total number of seats is odd or less than 2, there is no valid way to divide the corridor. Forgetting to check these conditions at the start leads to incorrect results or division by zero errors when computing gap products.

Misunderstanding Where Dividers Can Be Placed

Dividers can only be placed between sections, specifically in the gaps between the second seat of one section and the first seat of the next section. The number of valid positions for each divider equals the number of positions between consecutive seat pairs (the gap includes all plants plus the implicit space between seats).

Off-by-One Errors in Gap Calculation

The gap between the 2nd seat of one section and the 1st seat of the next is seats[i+1] - seats[i], not seats[i+1] - seats[i] - 1 or seats[i+1] - seats[i] + 1. This represents the number of possible divider positions, including placing it immediately after the 2nd seat.

Forgetting to Apply Modulo During Multiplication

The product of gaps can become extremely large. Applying modulo only at the end causes integer overflow. You must apply modulo after each multiplication step to keep the intermediate results within bounds.

Incorrect Loop Bounds in Combinatorics Approach

When iterating through seat positions to compute gap products, the loop should process pairs (seats[1], seats[2]), (seats[3], seats[4]), etc. Starting at the wrong index or using incorrect step sizes skips gaps or includes invalid pairs.