Problem

Along a long library corridor, there is a line of seats and decorative plants. You are given a 0-indexed string corridor of length n consisting of letters 'S' and 'P' where each 'S' represents a seat and each 'P' represents a plant.

One room divider has already been installed to the left of index 0, and another to the right of index n - 1. Additional room dividers can be installed. For each position between indices i - 1 and i (1 <= i <= n -1), at most one divider can be installed.

Divide the corridor into non-overlapping sections, where each section has exactly two seats with any number of plants. There may be multiple ways to perform the division. Two ways are different if there is a position with a room divider installed in the first way but not in the second way.

Return the number of ways to divide the corridor. Since the answer may be very large, return it modulo 10^9 + 7. If there is no way, return 0.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


![](https://assets.leetcode.com/uploads/2021/12/04/1.png)

    
    
    Input: corridor = "SSPPSPS"
    Output: 3
    Explanation: There are 3 different ways to divide the corridor.
    The black bars in the above image indicate the two room dividers already installed.
    Note that in each of the ways, **each** section has exactly **two** seats.

Example 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


![](https://assets.leetcode.com/uploads/2021/12/04/2.png)

    
    
    Input: corridor = "PPSPSP"
    Output: 1
    Explanation: There is only 1 way to divide the corridor, by not installing any additional dividers.
    Installing any would create some section that does not have exactly two seats.

Example 3

1
2
3
4
5
6
7
8
9


![](https://assets.leetcode.com/uploads/2021/12/12/3.png)

    
    
    Input: corridor = "S"
    Output: 0
    Explanation: There is no way to divide the corridor because there will always be a section that does not have exactly two seats.

Constraints

  • n == corridor.length
  • 1 <= n <= 10^5
  • corridor[i] is either 'S' or 'P'.

Solution

Method 1 – Counting Gaps Between Seat Pairs

Intuition

We must divide the corridor into sections with exactly two seats each. The only places to put dividers are between pairs of seats, and the number of ways is the product of the number of possible divider positions (gaps) between each pair of seat groups.

Approach

  1. Count the total number of seats. If it’s not even or less than 2, return 0.
  2. For each group of two seats, count the number of plants between them (i.e., the number of ways to place a divider after each group).
  3. The answer is the product of all such gaps (plus one for each, since you can put a divider after any plant between seat pairs).
  4. Return the answer modulo 1e9+7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    int numberOfWays(string corridor) {
        const int mod = 1e9+7;
        int n = corridor.size(), seats = 0;
        for (char c : corridor) if (c == 'S') ++seats;
        if (seats == 0 || seats%2) return 0;
        long long ans = 1;
        int cnt = 0, i = 0;
        while (i < n && corridor[i] != 'S') ++i;
        for (; i < n; ++i) {
            if (corridor[i] == 'S') ++cnt;
            if (cnt == 2) {
                int j = i+1, plants = 0;
                while (j < n && corridor[j] != 'S') { ++plants; ++j; }
                if (j < n) ans = ans * (plants+1) % mod;
                cnt = 0; i = j-1;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func numberOfWays(corridor string) int {
    mod := int(1e9+7)
    seats := 0
    for _, c := range corridor {
        if c == 'S' { seats++ }
    }
    if seats == 0 || seats%2 != 0 { return 0 }
    ans := 1
    cnt, i, n := 0, 0, len(corridor)
    for i < n && corridor[i] != 'S' { i++ }
    for i < n {
        if corridor[i] == 'S' { cnt++ }
        if cnt == 2 {
            j, plants := i+1, 0
            for j < n && corridor[j] != 'S' {
                plants++
                j++
            }
            if j < n { ans = ans * (plants+1) % mod }
            cnt = 0; i = j-1
        }
        i++
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int numberOfWays(String corridor) {
        int mod = 1_000_000_007, n = corridor.length(), seats = 0;
        for (char c : corridor.toCharArray()) if (c == 'S') seats++;
        if (seats == 0 || seats%2 != 0) return 0;
        long ans = 1;
        int cnt = 0, i = 0;
        while (i < n && corridor.charAt(i) != 'S') i++;
        for (; i < n; i++) {
            if (corridor.charAt(i) == 'S') cnt++;
            if (cnt == 2) {
                int j = i+1, plants = 0;
                while (j < n && corridor.charAt(j) != 'S') { plants++; j++; }
                if (j < n) ans = ans * (plants+1) % mod;
                cnt = 0; i = j-1;
            }
        }
        return (int)ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun numberOfWays(corridor: String): Int {
        val mod = 1_000_000_007
        val n = corridor.length
        var seats = 0
        for (c in corridor) if (c == 'S') seats++
        if (seats == 0 || seats%2 != 0) return 0
        var ans = 1L
        var cnt = 0; var i = 0
        while (i < n && corridor[i] != 'S') i++
        while (i < n) {
            if (corridor[i] == 'S') cnt++
            if (cnt == 2) {
                var j = i+1; var plants = 0
                while (j < n && corridor[j] != 'S') { plants++; j++ }
                if (j < n) ans = ans * (plants+1) % mod
                cnt = 0; i = j-1
            }
            i++
        }
        return ans.toInt()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def numberOfWays(self, corridor: str) -> int:
        mod = 10**9+7
        seats = corridor.count('S')
        if seats == 0 or seats%2:
            return 0
        ans, cnt, i, n = 1, 0, 0, len(corridor)
        while i < n and corridor[i] != 'S':
            i += 1
        while i < n:
            if corridor[i] == 'S':
                cnt += 1
            if cnt == 2:
                j, plants = i+1, 0
                while j < n and corridor[j] != 'S':
                    plants += 1
                    j += 1
                if j < n:
                    ans = ans * (plants+1) % mod
                cnt = 0
                i = j-1
            i += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

impl Solution {
    pub fn number_of_ways(corridor: String) -> i32 {
        let modv = 1_000_000_007;
        let n = corridor.len();
        let s = corridor.as_bytes();
        let seats = s.iter().filter(|&&c| c == b'S').count();
        if seats == 0 || seats%2 != 0 { return 0; }
        let mut ans = 1i64;
        let mut cnt = 0; let mut i = 0;
        while i < n && s[i] != b'S' { i += 1; }
        while i < n {
            if s[i] == b'S' { cnt += 1; }
            if cnt == 2 {
                let mut j = i+1; let mut plants = 0;
                while j < n && s[j] != b'S' { plants += 1; j += 1; }
                if j < n { ans = ans * (plants+1) % modv; }
                cnt = 0; i = j-1;
            }
            i += 1;
        }
        ans as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    numberOfWays(corridor: string): number {
        const mod = 1_000_000_007
        const n = corridor.length
        let seats = 0
        for (const c of corridor) if (c === 'S') seats++
        if (seats === 0 || seats%2 !== 0) return 0
        let ans = 1, cnt = 0, i = 0
        while (i < n && corridor[i] !== 'S') i++
        while (i < n) {
            if (corridor[i] === 'S') cnt++
            if (cnt === 2) {
                let j = i+1, plants = 0
                while (j < n && corridor[j] !== 'S') { plants++; j++ }
                if (j < n) ans = ans * (plants+1) % mod
                cnt = 0; i = j-1
            }
            i++
        }
        return ans
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of corridor.
  • 🧺 Space complexity: O(1), only a few variables are used.